Binary heaps
A heap is another variant of a tree, which exists in two versions: min-heap and max-heap. For each of them, an additional property must be satisfied:
- For min-heap: The value of each node must be greater than or equal to the value of its parent node
- For max-heap: The value of each node must be less than or equal to the value of its parent node
These rules perform a very important role, because they dictate that the root node always contains the smallest (in the min-heap) or the largest (in the max-heap) value. For this reason, it is a convenient data structure for implementing a priority queue, described in Chapter 3, Stacks and Queues.
Heaps come in many variants, including binary heaps, which are the topic of this section. In this case, a heap must comply to one of the previously-mentioned rules (depending on the kind: min-heap or max-heap) and it must adhere to the complete binary tree rule, which requires that each node cannot contain more than two children, as well as all levels...