We describe a number of alternative implementations for the heap
functions, which are part of the C++ standard library, and
provide a through experimental evaluation of their performance. In our
benchmarking framework the heap functions are implemented using the
same set of utility functions, the utility functions
using the same set of policy functions, and for each implementation
alternative only the utility functions need be modified. This way the
programs become homogeneous and the underlying methods can be
Our benchmarks show that the conflicting results in earlier
experimental studies are mainly due to test arrangements.
No heapifying approach is universally the best for all kinds of
inputs and ordering functions, but the
bottom-up heapifying performs well for most kinds of inputs and ordering
functions. We examine several
approaches that improve the worst-case performance
and make the heap functions even more trustworthy.