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

A Complete Binary tree is a tree where each node has at most two children and the nodes at all levels are full, except for the leaf nodes which can be empty.

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, it is the left child of its parent
5. If the singular child exists, it is the rightmost leaf at depth $d$.

The Heap Order Property

The nodes must be ordered according to the Heap Order Property. 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:

...