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.

Applying the heap order property

A heap is built based on the heap order property. In heap order property, you compare the parent node key with its child node keys. The heap order property is different for the two heap structures that you are going to study in this chapter:

• Min heap
• Max heap

Min heaps are built based upon the min heap property, and max heaps are built based upon max heap property. See how they are different which is explained in the next section.

Max heap property

All the parent node keys must be greater than or equal to their child node keys in max heaps. Therefore, the root node will always contain the largest element in the heap. If node A has a child called node B, then:

$$key(A)>=key(B)$$ ...