This report is intended to be used as graduate level course material on the subject of heaps. The text is organised as a sequence of lectures (chapters), each giving an overview of a specific aspect or variation of the heap data structure. Along with each chapter is given one or more implementations of the ideas presented in the chapter, and the actual performance and usability is compared to other heap implementations, by means of what I call Heaplab.
Heaplab is nothing but a directory structure, a makefile, and a few driver programs, which allows experiments with heaps to be conducted easily. The driver programs verifies that the heap implementation actually works, both as an priority queue and as a sorting tool, through an external test. The driver programs also times the heap implementations and reports the results in a format well suited to gnuplot. This hopefully ensures that comparisons are done in a unified way and with correct programs. The details of heaplab are described in appendix A. Heaplab is written in C++ [10] and expects the heap implementation to be written in C++ too.