16

What is the right data structure for a queue that support Enque, Dequeue, Peak, Min, and Max operation and perform all these operations in O(1) time.

The most obvious data structure is linked list but Min, Max operations would be O(n). Priority Queue is another perfect choice but Enqueue, Dequeue should works in the normal fashion of a Queue. (FIFO)

And another option that comes to mind is a Heap, but I can not quite figure out how one can design a queue with Min, Max operation using Heaps.

Any help is much appreciated.

Improve this question
8
  • I am not sure that such a data structure exist. You might want to mix queue and trie (or some kind of balanced trees), but some operations would take O(log(n)) Commented Apr 16, 2015 at 13:11
  • Also, programmers is probably a better place to ask. Commented Apr 16, 2015 at 13:15
  • It is possible to design a Stack that met all these requirements. By storing the Min and Max value for up to each element we can find the Min and Max in O(1) time, but with queue it is trickier. I think there should be a way, because I know someone who have implemented this. But I don't know how. Commented Apr 16, 2015 at 13:16
  • 2
    No, if you pop the Min or the Max value, your Stack is not O(1) Commented Apr 16, 2015 at 13:18
  • 1
    The question is not entirely clear: do min() and max() remove elements from the structure, or are they read-only?. If read-only, then an O(1) stack-with-min-max is certainly possible (however, not a queue). If not read-only, then @BasileStarynkevitch is right, and such structure will not work as intended. Commented Apr 22, 2015 at 12:09

4 Answers 4

Reset to default
7
+50

The data structure you seek cannot be designed, if min() and max() actually change the structure. If min() and max() are similar to peek(), and provide read-only access, then you should follow the steps in this question, adding another deque similar to the one used for min() operations for use in max() operation. The rest of this answer assumes that min() and max() actually remove the corresponding elements.

Since you require enqueue() and dequeue(), elements must be added and removed by order of arrival (FIFO). A simple double-ended queue (either linked or using a circular vector) would provide this in O(1).

But the elements to be added could change the current min() and max(); however, when removed, the old min() and max() values should be restored... unless they were removed in the interim. This restriction forces you to keep elements sorted somehow. Any sorting structure (min-heap, max-heap, balanced binary tree, ...) will require at least O(log n) to find the position of a new arrival.

Your best bet is to pair a balanced binary tree (for min() and max()) with a doubly-linked list. Your tree nodes would store a set of pointers to the list nodes, sorted by whatever key you use in min() and max(). In Java:

// N your node class; can return K, comparable, used for min() and max() LinkedList<N> list; // sorted by arrival TreeMap<K,HashMap<N>> tree; // sorted by K
  • on enque(), you would add a new node to the end of list, and add that same node, by its key, to the HashMap in its node in tree. O(log n).
  • on dequeue(), you would remove the node from the start of list, and from its HashMap in its node in tree. O(log n).
  • on min(), you would look for the 1st element in the tree. O(1). If you need to remove it, you have the pointer to the linked list, so O(1) on that side; but O(log n) to re-balance the tree if it was the last element with that specific K.
  • on max(), the same logic applies; except that you would be looking for the last element in the tree. So O(log n).
  • on peek(), looking at but not extracting the 1st element in the queue would be O(1).

You can simplify this (by removing the HashMap) if you know that all keys will be unique. However, this does not impact asymptotic costs: they would all remain the same.

In practice, the difference between O(log n) and O(1) is so low that the default map implementation in C++'s STL is O(log n)-based (Tree instead of Hash).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

6

Any data structure that can retrieve Min or Max in O(1) time needs to spend at least O(log n) on every Insert and Remove to maintain elements in partially sorted order. The data structures that do achieve this are called priority queues.

The basic priority queue supports Insert, Max, and RemoveMax. There are a number of ways to build them, but binary heaps work best.

Supporting all of Insert, Min, RemoveMin, Max, and RemoveMax with a single priority queue is more complex. A way to do this with a single data structure, adapted from a binary heap, is described in the paper:

Atkinson, Michael D., et al. "Min-max heaps and generalized priority queues." Communications of the ACM 29.10 (1986): 996-1000.

It is fast and memory-efficient, but requires a good amount of care to implement correctly.

Improve this answer

Comments

1

This structure DOES NOT exist!

There is a simple way to approve this conclusion.

As we all know,the complexity of sorting problem is O(nlogn). But if the structure you said exists,there will be a solution for sorting:

  1. Enque every element one by one costs O(n)
  2. Dequeue every max(or min) element one by one costs O(n)

which means the sorting problem can be solved by O(n).But it is IMPOSSIBLE.

Improve this answer

4 Comments

Nice proof -- any structure that implements modifying min() or max() would mean a big breakthrough in sorting. On the other hand, it is not clear whether the OP meant "read-only" min() and max().
Good start to a proof, but not fully flushed out. Your assumption seams to be that we do not have a sorted list. Doubly linked list removes disproves #2 alone. This also seams to assume that the structure cannot have meta info about its location in a queue. I will grant that proving the not is extremely hard with algorithms. Maybe a few more iterations, and this could be proven. but its far from impossible.
I consider this "proof that such a structure would be a huge breakthrough in sorting", rather than "proof that such a structure is impossible". In the first sense, it is ironclad: if you can insert in O(n) and removeMin in O(n), you can sort in O(n) (!!). In the second sense, proving that it is "impossible" to sort in less than O(n log n) is much harder than making @lessmoon's observation. However, many very smart people have tried to improve O(n log n), and it is a pretty safe bet that it cannot be improved. Proven for binary-comparison swap-based algorithms, too.
humm, the last line "which means the sorting problem can be solved by O(n).But it is IMPOSSIBLE." seamed to "proof that such a structure is impossible." I guess its on interpretation. Good luck with proofs in the future.
-2

Assumptions:

that you only care about performance and not about space / memory / ...

A solution:

That the index is a set, not a list (will work for list, but may need some extra love)

You could do a queue and a hash table side by side.

Example:

Lets say the order is 5 4 7 1 8 3

Queue -> 547813

Hash table -> 134578

Enqueue:

1) Take your object, and insert into the hash table in the right bucket Min / Max will always be the first and last index. (see sorted hash tables)

2) Next, insert into your queue like normal.

3) You can / should link the two. One idea would be to use the hash table value as a pointer to the queue.

Both operations with large hash table will be O(1)

Dequeue:

1) Pop the fist element O(1)

2) remove element from hash table O(1)

Min / Max:

1) Look at your hash table. Depending on the language used, you could in theory find it by looking at the head of the table, or the tail of the table.

For a better explanation of sorted hash tables, https://stackoverflow.com/questions/2007212

Note: I would like to note, that there is no "normal" data structure that will do what you are requiring that I know of. However, that does not mean it is not possible. If you are going to attempt to implement the data structure, most likely you will have to do it for your needs and will not be able to use current libraries available. You may have to look at using a very low level language like assembly in order to achieve this, but maybe C or Java might be able to if your good with those languages.

Good luck

EDITED: I did not explain sorted hash tables, so added a link to another SO to explain them.

Improve this answer

9 Comments

You are mixing up hash tables (no order guarantee) and tree maps (order guaranteed, but O(log n) instead of O(1)). The "head" and "tail" of a hashtable bear no relation to min/max
Depends on the hash table that you use. if you use a 1 to 1 hash table where the insert is on the value, then no. for example, if my number range is 1 to 10, and my map is 1 to 10, I could have the values do an insert on the row in the table. Since most arrays inserts are not O(1), i did not do it that way. Your assumption is that the hash keys are not related to the values, which is normal, however, not always true. On insert of value 10, you insert in to row 10, on value 2 you insert into row 2. Ill edit the answer to explain that portion better.
Updated post to point to sorted hash tables. There not a 'standard' way to do such, so the OP will have to figure it out based off of the OP situation.
Sorry Jdhaern, but the linked question does not explain "sorted hash tables" - it merely requests them. Such creatures do not exist. Its accepted answer points to a TreeMap (not hashed in any way, and O(log n) for all operations). Your answer still mixes the low cost of HashMaps with the order-preserving qualities of TreeMaps; it is still a wrong answer.
Did you read the answers? My not have "explained" them, but got you some one there. Its very tricky since it involves many pointers. And I do understand that you are coming from a Java background, think lower level. Also, its not a "normal" hash map. You would have to have some sort of other data structure involved to help out. And you should look at TreeMaps as well. as they are not any where close to what I am describing. You have 100 rows, and you insert into the rows on the value of the object. that is not a TreeMap.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.