Menu
I'm looking for algorithms like ones in the stl (push_heap, pop_heap, make_heap) except with the ability to pop both the minimum and maximum value efficiently. AKA double ended priority queue. As described here.
Any clean implementation of a double ended priority queue would also be of interest as an alternative, however this question is mainly about a MinMax Heap implementation.
My google-fu has not been fruitful, but surely, it must exist?
514
To heapify an element in a max heap we need to find the maximum of its children and swap it with the current element. We continue this process until the heap property is satisfied at each node. In order to heapify we move down from the root to the leaves.
A max heap is a data structure in which each child node is less than or equal to its parent node. A min heap is a similar type of data structure where each child node is greater than or equal to its parent node.
Like binary min-heaps and max-heaps, min-max heaps support logarithmic insertion and deletion and can be built in linear time.
Is there a reason you can't use std::set? It sounds like that, along with some wrappers to access and remove set::begin() and --set::end() will solve the problem. I imagine it will be difficult to find something that can generally do a MinMax Heap much faster than the default implementation of set.
96
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
