How can I implement a double ended priority queue with O(log(n)) complexity of insertion, find min and find max operations?
I was thinking of using a red black tree, but it is a little bit complicated. Is there a simpler alternative?
I have also heard of a double ended heap, but the complexity of finding or deleting the min and max seems to be be linear and not logarithmic.
2
Here is what I did for a block allocator free-list implementation that needed a double-ended priority queue:
- Use standard red-black tree algorithms, with one small enhancement:
- During insertion keep track of the minimum and maximum element in the tree as you do insertions or deletions. This only adds at most O(log n) comparisons as overhead during the already O(log n) insertion process, so doesn’t change the overall algorithmic complexity.
This yields:
- O(log n): insertion
- O(1): find-min and delete-min
- O(1): find-max and delete-max
Since those were the only operations I needed for my particular application, this was pretty much the best possible data structure. Even if you needed other priority queue operations (like changing priorities, etc) pretty much everything is still going to be O(log n) worst case because of the red-black tree.
The reason you get O(1) for both find-min/max as well as delete-min/max is that you’ve kept track of the minimum and maximum element during insertion, so you can immediately find it, eliminating the O(log n) for the search. Then the red-black tree algorithm guarantees O(1) operations to rebalance the tree after the element is removed. (This is a well known and very important property of red-black trees. This wouldn’t be the case with most other binary search trees, such as AVL trees, which require O(log n) operations during rebalancing.)