What is a Heap?

Introduction

Heaps are advanced data structures that are useful in applications where you want to sort and implement 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$.