Is there a C++ MinMax Heap implementation?

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.

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

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