10. Heaps

In this chapter, we discuss two implementations of the extremely useful
priority `Queue` data structure. Both of these structures are a special
kind of binary tree called a heap,
which means ``a disorganized
pile.'' This is in contrast to binary search trees that can be thought
of as a highly organized pile.

The first heap implementation uses an array to simulate a complete binary tree. This very fast implementation is the basis of one of the fastest known sorting algorithms, namely heapsort (see Section 11.1.3). The second implementation is based on more flexible binary trees. It supports a operation that allows the priority queue to absorb the elements of a second priority queue .

- 10.1
`BinaryHeap`: An Implicit Binary Tree - 10.2
`MeldableHeap`: A Randomized Meldable Heap - 10.3 Discussion and Exercises

opendatastructures.org