Is there a C++ MinMax Heap implementation?

Question

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?

Solution 1

If you're looking for the algorithm implementation try searching Github.

Solution 2

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.

Solution 3

I can't find any good implementations, but since no one else can either I'm guessing you'll be writing your own, in which case I have a few handy references for you.

A paper that no one seems to have mentioned is the original proposition for Min-Max-Heaps:

http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf

I've implemented a min-max heap from this paper twice (not in C) and found it fairly trivial.

An improvement, which I haven't ever implemented, is a Min-Max-Fine-Heap. I can't find any good papers or references on a plain old fine heap, but I did find one on the min-max-fine-heap, which apparently performs better:

http://arxiv.org/ftp/cs/papers/0007/0007043.pdf

Comments

[porgarmingduod]

Using std::set like you suggest is a workaround. It may be fine, but the MinMax heap would be the optimal solution for my problem, which is why I am asking for it specifically. But it's useful to keep in mind that std::set does more or less the same thing, so thanks for pointing it out.

[Slauma]

Perhaps lack of a unique key ? The keys in a set it is sorted by must be unique but not in a priority queue or double ended priority queue.

[Slauma]

But nonetheless: This answer was very useful since I was never aware that the elements in a set or map are SORTED! I was believing that set and map were simply unsorted associative containers which only guarantee the uniqueness of keys but nothing more.

[JonM]

@Slauma There's also std::multiset.

[josesuero]

Yeah, multiset sounds like it'd do what you need

[Antti Huima]

But for large heaps / lots of operations the set implementation will be slower than a minimax heap... a minimax heap has the same time complexity as a normal heap, i.e. has O(1) find-min / find-max operations whereas for a general set implementation find-min and find-max are typically O(log n).

[porgarmingduod]

I actually found a different (and improved) approach to my problem that didn't require a MinMax Heap. I just put a bounty on the question hoping something useful would come out of this. I already found that paper you link by the way, but it's a good thing you added it here for reference.

[ICTMitchell]

@antti: If you overload insert you can cache max/min element after insert, and thus have O(log n) insert but O(1) get max/min.

[Admin]

I've upvoted antti.huimas comment, but it could be premature optimisation. Abstract the queue, maybe, so that the implementation can be swapped out if genuinely needed. Or don't - the refactoring to swap it out if needed probably won't be much anyway. Also, I believe that finding the end-points in std::set is actually O(1) anyway - that the set object actually holds pointers to the min and max nodes as well as the root, so that begin() and end() are handled efficiently.

[JonM]

+1 for the first document which is well written with some useful psuedocode.

[GManNickG]

Sorry, have to -1 this. The first 3 #define lines alone are undefined behavior (why are you redefining bool, true, and false?), the following lines are bad style (use functions), and you rewrote swap for no reason (that's an incorrect implementation, by the way; consider when a == b). Good for providing an implementation, but I personally don't think a bad implementation is better than none.

[AmeyaVS]

The hyperlink is broken, making this answer is obsolete.

[Eugen Constantin Dinca]

@AmeyaVS Got it. Updated to GH search.