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 compared fairly.

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.

@report{JKV2003R,
  author = {Claus Jensen and Jyrki Katajainen and Fabio Vitale},
  title = {An extended truth about heaps},
  type = {CPH STL Report},
  number = {2003-5},
  institution = {Department of Computer Science, University of Copenhagen},
  year = {2003},
  pagetotal = {16},
}