What is the right data structure for a queue that support Min, Max operations in O(1) time?

Question

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.

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)) — Basile Starynkevitch
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. — bman
No, if you pop the Min or the Max value, your Stack is not O(1) — Basile Starynkevitch
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. — tucuxi

tucuxi tucuxi · Accepted Answer · 2015-04-22T11:16:20

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).

What is the right data structure for a queue that support Min, Max operations in O(1) time?

4 Answers