What is a Heap?

Introduction

Heaps are advanced data structures that are useful in applications such as sorting and implementing priority queues. They are regular binary trees with two special properties:

• Heaps must be complete binary trees.
• The nodes must be ordered according to the heap order property.

📝 Heaps are binary trees. Therefore, sometimes they are called binary heaps.

Heaps must be complete binary trees

As discussed in the trees chapter, a complete binary tree is a binary tree in which all the levels of the tree are fully filled, except for perhaps the last level, which can be filled from left to right.

Some complete binary tree properties:

1. All leaves are either at depth $d$ or depth $d-1$.
2. The leaves at depth $d$ are to the left of the leaves at depth $d-1$.
3. There is (at most) one node with just one child.
4. If the singular child exists, then it is the left child of its parent.