Heaps
A heap is another variant of a tree, which you already got to know in Chapter 3, Arrays and Sorting. There, you used a heap in the heap sort algorithm for sorting an array. For this reason, in the current chapter, you will see only a brief summary of this data structure. However, I strongly encourage you not to leave this topic and learn much more about heaps on your own, as they are powerful and popular data structures.
As you already know, a binary heap 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 value (in the min-heap) or the largest value (in the max-heap). You benefited from this assumption...
