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