<p>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.</p>

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

<p><a href="http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf" rel="nofollow noreferrer">http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf</a></p>

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

<p>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:</p>

<p><a href="http://arxiv.org/ftp/cs/papers/0007/0007043.pdf" rel="nofollow noreferrer">http://arxiv.org/ftp/cs/papers/0007/0007043.pdf</a></p>
Is there a C++ MinMax Heap implementation?
<p>I'm looking for algorithms like ones in the stl (<code>push_heap</code>, <code>pop_heap</code>, <code>make_heap</code>) except with the ability to pop both the minimum and maximum value efficiently. AKA double ended priority queue. As described <a href="http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node11.html" rel="noreferrer">here</a>. </p>

<p>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.</p>

<p>My google-fu has not been fruitful, but surely, it must exist?</p>