Min-max heap

The min-max heap is a data structure with constant time insertion, constant time querying and efficient deletion of both the smallest and the largest element. This specific implementation follows the format of the standard STL heap (std::heap). It uses no memory allocation functions or other system calls and is therefore safe to use in real-time applications. A possible application is a real-time priority queue of fixed length; the smallest element can be popped in order to not exceed the fixed length, while the largest element is (repeatedly) popped for processing.

Files

The min-max heap in STL format: stl_minmaxheap.h

Utility file with fast x86 log2 functions: ilog2.h

Todo

While the original stl_heap.h code wasn't pretty to start with, this extension made it worse. However, it works (thoroughly tested) and it's very fast. But a code cleanup would be nice.

The functions in ilog2.h are used to determine the level of a heap element. This dependency can probably be removed and replaced by something that has equal or better performance and no x86 dependency. A small loop would probably suffice for not too large heaps:

for (int i = 2; i <= __holeIndex; i *= 2 )

level++;

Authors

Contact Erik Schuitema for comments, bug reports and suggestions.