Is there a C++ MinMax Heap implementation?

views:

706

answers:

+6 Q:

Is there a C++ MinMax Heap implementation?

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?

+4 A:

My google-fu has led me to this:

Header file

Implementation file

Example

Manuel 2010-02-12 15:56:02

I swear I entered the exact same query as you. I guess google.es is just better. ;)

2010-02-12 16:19:25

Can't say I really like that implementation though. It doesn't even have a license, and I'm not sure how much I trust some random code written for a school project.

2010-02-12 16:39:18

Yeah the `#include "MinMaxHeap.C"` part is kind of unsettling :)

Manuel 2010-02-12 16:44:53

Probably better to use the `std::set` solution than this. But +1

Billy ONeal 2010-02-14 17:58:26

+7 A:

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.

JonM 2010-02-12 18:22:27

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.

2010-02-12 19:30:20

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 2010-02-12 19:33:31

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.

Slauma 2010-02-12 19:38:14

@Slauma There's also `std::multiset`.

JonM 2010-02-12 19:44:24

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

jalf 2010-02-14 22:56:01

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).

antti.huima 2010-02-16 23:47:14

@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.

Marcus Lindblom 2010-02-19 12:10:19

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.

Steve314 2010-02-21 12:30:08

+2 A:

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

Martin 2010-02-17 00:14:14

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.

2010-02-17 00:42:57

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

JonM 2010-02-22 00:10:16

+4 A:

If you're looking for algorithm implementation try directly Google Code Search.

Eugen Constantin Dinca 2010-02-17 08:22:14

I'm curious: why make your answer community wiky?

Manuel 2010-02-17 08:26:47

Thought that people might want to add more Code Search engines...

Eugen Constantin Dinca 2010-02-17 16:11:40

+1 A:

Not sure if this is exactly what you're looking for, but here is a MinMax Heap i created back in my university days. This was part of a larger project so, there is an extraneous reference on a 'Stopwatch' class which measured performance. I'm not including this class as it isn't my work. It isn't hard to strip it out so i'm leaving the reference to it as it is.

The code on snipplr

To use, just create a new instance of the heap with whatever type you want to use. (Note, custom types would need to overload comparison operators). Create array of that type and then pass it to the constructor and specify the current array size and what the maximum should be. This implementation works on top of a passed array only since this is the only thing i needed, but you have everything you need to implement push and pop methods.

Sergey 2010-02-21 18:07:40

ansaurus

tags:

views:

answers:

Is there a C++ MinMax Heap implementation?

related questions