This is where we go from O(n²) sorting and list-based priority queues to the O(log n) power of the heap.

What is a Binary Heap?

A Binary Heap is:

1. A complete binary tree → filled top-to-bottom, left-to-right
2. Each node stores a key (priority value)
3. It follows the heap-order property

It’s used mainly for:

• Implementing a Priority Queue
• Running Heap Sort

Complete Binary Tree

A complete binary tree is one that grows in breadth-first order:

Level 0: 1
Level 1: 2   3
Level 2: 4   5   6   7
Level 3: 8 9 10 11 12 13 14 15

Each new node fills from left to right before starting a new level.

This property makes the heap easy to store in an array rather than in explicit node objects:

Heap-Order Property