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