I'm trying to implement a binary heap (priority queue) that has the capabilities of both a min heap and a max heap. It needs to have an insert(value), extractMin(), and an extractMax() method. The extract methods remove the value from the heap and return the value.
I was originally using two arrays, called minHeap and maxHeap, one to store the data in a min heap structure, and the other to store the same data in a max heap structure. So when I call extractMin(), it removes and returns the value from minHeap. Then I have to remove that value from maxHeap as well (and vice-versa if I called extractMax()) in order to keep the data set identical in both heaps. And because of the heap-order property, it's guaranteed that I'll find that value in the leaves of the other heap. Searching for that value in the other heap results in a time complexity of O(n) or more precisely, O(n/2) since I'll only be searching the leaves. Not to mention, the percolatingDown() and percolatingUp() methods to restore the heaps after removing values is already O(log n); so in total, the extract methods would be O(n). The problem is, I need the extract methods to be O(log n).
Is there a better way to go about this?
I also thought of this idea but wanted to know what you all think first.
I just finished coding a "median heap" by placing the smaller half of the data in the max heap and the larger half in the min heap. With that structure, I'm able to easily retrieve the median of a given set of values. And I was thinking of using a similar structure of placing the smaller half of the data in the min heap and the larger half in the max heap and using the mean (rather than the median) of all the values to be the deciding factor of whether to place the value in the max or min heap when calling insert(value). I think this might work as the extract methods would stay O(log n).
The simple way is to just use a binary search tree, as M. Shaw recommends.
If you're required to build this on top of binary heaps, then in each heap, alongside each element, store the element's position in the other heap. Every time you move an element in one heap, you can go straight to its position in the other heap and update it. When you perform a delete-min or delete-max, no expensive linear scan in the other heap is required.
For example, if you store std::pairs with first as the element value and second as the position in the other heap, swapping two elements in the min-heap while updating their counterparts in the max-heap might look like this:
swap(minheap[i], minheap[j]);
maxheap[minheap[i].second].second = i;
maxheap[minheap[j].second].second = j;