What is the best way to implement a double-ended priority queue?
algorithm, big-o, data-structures, heapsort, priority-queue
Solution
There are many specialized data structures for this. One simple data structure is the min-max heap, which is implemented as a binary heap where the layers alternate between "min layers" (each node is less than or equal to its descendants) and "max layers" (each node is greater than or equal to its descendants.) The minimum and maximum can be found in time O(1), and, as in a standard binary heap, enqueues and dequeues can be done in time O(log n) time each.
You can also use the interval heap data structure, which is another specialized priority queue for the task.
Alternatively, you can use two priority queues - one storing elements in ascending order and one in descending order. Whenever you insert a value, you can then insert elements into both priority queues and have each store a pointer to the other. Then, whenever you dequeue the min or max, you can remove the corresponding element from the other heap.
As yet another option, you could use a balanced binary search tree to store the elements. The minimum and maximum can then be found in time O(log n) (or O(1) if you cache the results) and insertions and deletions can be done in time O(log n). If you're using C++, you can just use `std::map` for this and then use `begin()` and `rbegin()` to get the minimum and maximum values, respectively.
Hope this helps!
Problem
I would like to implement a double-ended priority queue with the following constraints: needs to be implemented in a fixed size array..say 100 elements..if new elements need to be added after the array is full, the oldest needs to be removed need maximum and minimum in O(1) if possible insert in O(1) if possible remove minimum in O(1) clear to empty/init state in O(1) if possible count of number of elements in array at the moment in O(1) I would like O(1) for all the above 5 operations but its not possible to have O(1) on all of them in the same implementation. Atleast O(1) on 3 operations and O(log(n)) on the other 2 operations should suffice. Will appreciate if any pointers can be provided to such an implementation.