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

The nodes must be ordered according to the Heap Order Property #

A heap is built based on the Heap Order property. In Heap Order property, we compare the parent node key with its child node keys. The heap order property is different for the two heap structures that we 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. Let’s see how they are different.

Max Heap Property:

All the parent node keys must be greater than or equal to their child node keys in max-heaps. So the root node will always contain the largest element in the Heap. If Node A has a child node B, then,

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