UNIT 13Prerequisite: Unit 12 — BST75 min read
A BST organises data so you can search efficiently. A heap organises data so you can always get the largest or smallest element instantly — in O(1). That one difference makes heaps the perfect tool for a completely different set of problems: priority queues, scheduling, and the fastest known sorting algorithm based on comparisons.
The best part: a heap is always a complete binary tree, which means it is always balanced. Unlike BSTs that can degrade to O(n), every heap operation is guaranteed O(log n) — no special handling, no self-balancing needed.
// Section 1
What is a Heap?
A heap is a complete binary tree that satisfies the heap property. Two things to unpack there. Let us start with each one.
Complete Binary Tree
All levels are fully filled except possibly the last, and the last level fills from left to right with no gaps. This guarantees the height is always O(log n) — the tree can never go skewed.
Heap Property
Max-heap: every parent is ≥ its children.
Min-heap: every parent is ≤ its children.
The root is always the maximum (max-heap) or minimum (min-heap).
Max-Heap — largest at root
Every parent ≥ its children ✓
Root = 90 = maximum element
Min-Heap — smallest at root
Every parent ≤ its children ✓
Root = 10 = minimum element
💡 Note
Heap vs BST — key difference: In a BST, inorder traversal gives sorted output because left < root < right at every node. In a heap, only the parent-child relationship is guaranteed — siblings have no defined order. A heap is not searchable like a BST. It is optimised for one thing: instantly getting the max or min.
// Section 2
Storing a Heap as an Array — The Clever Trick
Because a heap is always a complete binary tree, we never need to store left/right pointers. We can store the entire tree in a plain array — level by level, left to right. The parent-child relationships are calculated with simple index arithmetic. This makes heaps extremely memory-efficient and cache-friendly.
// Max-heap stored as array — level by level, left to right
Array representation (0-indexed):
parent(i) = (i-1)/2
parent(3) = (3-1)/2 = 1 → node 70 ✓
left(i) = 2*i + 1
left(1) = 2*1+1 = 3 → node 40 ✓
right(i) = 2*i + 2
right(1) = 2*1+2 = 4 → node 60 ✓
🎯 Pro Tip
Why does this work? Because the heap is always complete, there are never any gaps in the array. Every index from 0 to n-1 is used. The formulas above are just mathematics of a complete binary tree — they always hold regardless of the heap's values.
// Section 3
Insert — Add and Bubble Up
To insert into a max-heap: place the new element at the end of the array (the next available position in the complete tree), then bubble it up — repeatedly swap it with its parent as long as it is larger than its parent. This restores the heap property from the bottom up.
// Inserting 80 into max-heap [90, 70, 50, 40, 60, 20, 30]
Step 1: Place 80 at index 7 (end)
Step 2: parent(7)=3, arr[3]=40 < 80 → swap
Step 3: parent(3)=1, arr[1]=70 < 80 → swap
Step 4: parent(1)=0, arr[0]=90 > 80 → STOP ✓
#include <stdio.h>
#define MAX 100
struct MaxHeap {
int data[MAX];
int size;
};
typedef struct MaxHeap MaxHeap;
void initHeap(MaxHeap *h) { h->size = 0; }
int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
void insert(MaxHeap *h, int value) {
if (h->size == MAX) { printf("Heap full\n"); return; }
/* place at end */
h->data[h->size] = value;
int i = h->size;
h->size++;
/* bubble up: swap with parent while larger than parent */
while (i > 0 && h->data[i] > h->data[parent(i)]) {
swap(&h->data[i], &h->data[parent(i)]);
i = parent(i); /* move up to parent position */
}
}
void printHeap(MaxHeap *h) {
int i;
for (i = 0; i < h->size; i++) printf("%d ", h->data[i]);
printf("\n");
}
int main() {
MaxHeap h;
initHeap(&h);
insert(&h, 50);
insert(&h, 70);
insert(&h, 40);
insert(&h, 90);
insert(&h, 20);
printHeap(&h); /* 90 70 40 50 20 — root is always max */
printf("Max element: %d\n", h.data[0]); /* 90 */
return 0;
}
Time:O(log n)(at most height bubbles = log n swaps)
// Section 4
Delete Max — Extract Root and Heapify Down
Deleting from a heap always means removing the root — the maximum (or minimum). You cannot just remove the root and leave a hole. The strategy: move the last element to the root position, shrink the size by 1, then heapify down — push the misplaced root down by swapping with its larger child until the heap property is restored.
// Extracting max (90) from heap [90, 70, 50, 40, 60, 20, 30]
Step 1: Move last (30) to root. Remove old last.
Step 2: children=70,50. Larger=70 > 30 → swap with index 1
Step 3: children=40,60. Larger=60 > 30 → swap with index 4
Step 4: children of index 4 = none. Heap property restored ✓
/* push element at index i down to its correct position */
void heapifyDown(MaxHeap *h, int i) {
int largest = i;
int left = leftChild(i);
int right = rightChild(i);
/* find the largest among node, left child, right child */
if (left < h->size && h->data[left] > h->data[largest]) {
largest = left;
}
if (right < h->size && h->data[right] > h->data[largest]) {
largest = right;
}
/* if current node is not the largest — swap and continue down */
if (largest != i) {
swap(&h->data[i], &h->data[largest]);
heapifyDown(h, largest); /* recursively fix the affected subtree */
}
}
/* extract the maximum element (root) */
int extractMax(MaxHeap *h) {
if (h->size == 0) { printf("Heap empty\n"); return -1; }
int maxVal = h->data[0]; /* save the max value to return */
h->data[0] = h->data[h->size-1]; /* move last element to root */
h->size--; /* shrink heap */
heapifyDown(h, 0); /* restore heap property */
return maxVal;
}
int main() {
MaxHeap h;
initHeap(&h);
insert(&h, 90); insert(&h, 70); insert(&h, 50);
insert(&h, 40); insert(&h, 60); insert(&h, 20); insert(&h, 30);
printf("Extract: %d\n", extractMax(&h)); /* 90 */
printf("Extract: %d\n", extractMax(&h)); /* 70 */
printf("Extract: %d\n", extractMax(&h)); /* 60 */
printHeap(&h); /* remaining: 50 40 30 20 */
return 0;
}
Extract Max:O(log n)
Peek Max:O(1)(just read arr[0])
// Section 5
Build Heap — Turn Any Array into a Heap
If you have an existing unsorted array and want to make it a valid heap, you could insert elements one by one — O(n log n) total. But there is a smarter approach: heapify the array in-placeby applying heapifyDown to every non-leaf node, starting from the last one and moving to the root. This runs in O(n) — faster than n individual insertions.
/* build a max-heap from an existing unsorted array in O(n) */
void buildHeap(MaxHeap *h, int arr[], int n) {
int i;
/* copy array into heap */
for (i = 0; i < n; i++) h->data[i] = arr[i];
h->size = n;
/* start from last non-leaf node and heapify down each one
last non-leaf index = (n/2) - 1 */
for (i = (n / 2) - 1; i >= 0; i--) {
heapifyDown(h, i);
}
}
int main() {
int arr[] = {3, 9, 2, 1, 4, 5, 8, 7, 6};
int n = 9;
MaxHeap h;
buildHeap(&h, arr, n);
printHeap(&h);
/* Output: 9 7 8 6 4 5 2 1 3 — valid max-heap ✓ */
printf("Max: %d\n", h.data[0]); /* 9 */
return 0;
}
💡 Note
Why O(n) and not O(n log n)? Most nodes are near the bottom of the tree and only need to travel a short distance down. The mathematical sum of all these distances works out to O(n). This is one of the nicest results in algorithm analysis — and it is what makes heap sort practical.
// Section 6
Heap Sort — Sort Using a Heap
Heap sort uses the heap to sort an array in O(n log n) with O(1) extra space. It has two phases:
1
Build a max-heap from the array
O(n) — the array is now a valid max-heap. Largest element is at index 0.
2
Repeatedly extract the max
Swap root (max) with the last element, shrink heap size by 1, heapify down. The extracted max goes to the end of the array. Repeat n-1 times.
// Heap sort on [4, 10, 3, 5, 1] — step by step
Build heap: [4,10,3,5,1] → [10,5,3,4,1]
Pass 1: swap arr[0]=10 and arr[4]=1 → [1,5,3,4,10] → heapify → [5,4,3,1,10]
Pass 2: swap arr[0]=5 and arr[3]=1 → [1,4,3,5,10] → heapify → [4,1,3,5,10]
Pass 3: swap arr[0]=4 and arr[2]=3 → [3,1,4,5,10] → heapify → [3,1,4,5,10]
Pass 4: swap arr[0]=3 and arr[1]=1 → [1,3,4,5,10]
Result: 1 3 4 5 10 — sorted ✓
/* heap sort — sorts arr[] in ascending order in-place */
void heapSort(int arr[], int n) {
MaxHeap h;
/* phase 1: build max-heap from the array */
buildHeap(&h, arr, n);
/* phase 2: extract max one by one, place at end */
int i;
for (i = n - 1; i > 0; i--) {
/* move current max (root) to end of sorted portion */
swap(&h.data[0], &h.data[i]);
h.size--; /* shrink heap — sorted part grows */
heapifyDown(&h, 0); /* restore heap property */
}
/* copy sorted heap back to original array */
for (i = 0; i < n; i++) arr[i] = h.data[i];
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = 5;
int i;
printf("Before: ");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
heapSort(arr, n);
printf("\nAfter: ");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
/* After: 11 12 22 25 64 */
return 0;
}
Time (all cases):O(n log n)
Space:O(1)(in-place)
🎯 Pro Tip
Heap sort vs Quick sort: Heap sort guarantees O(n log n) even in the worst case — quick sort can degrade to O(n²). But quick sort is faster in practice due to better cache behaviour. Heap sort is used when you need a worst-case guarantee and cannot afford O(n²) under any circumstances.
// Section 7
Min-Heap — Smallest Always at Root
A min-heap is identical to a max-heap — same structure, same operations — except the heap property is reversed: every parent is ≤ its children. The root always holds the minimum element. To convert our max-heap code to a min-heap, just flip one comparison in heapifyDown and insert.
/* Min-heap — only the comparison direction changes */
void heapifyDownMin(MaxHeap *h, int i) {
int smallest = i;
int left = leftChild(i);
int right = rightChild(i);
/* find SMALLEST among node, left child, right child */
if (left < h->size && h->data[left] < h->data[smallest]) smallest = left;
if (right < h->size && h->data[right] < h->data[smallest]) smallest = right;
if (smallest != i) {
swap(&h->data[i], &h->data[smallest]);
heapifyDownMin(h, smallest);
}
}
void insertMin(MaxHeap *h, int value) {
h->data[h->size] = value;
int i = h->size++;
/* bubble UP while SMALLER than parent */
while (i > 0 && h->data[i] < h->data[parent(i)]) {
swap(&h->data[i], &h->data[parent(i)]);
i = parent(i);
}
}
int extractMin(MaxHeap *h) {
int minVal = h->data[0];
h->data[0] = h->data[--h->size];
heapifyDownMin(h, 0);
return minVal;
}
int main() {
MaxHeap h;
initHeap(&h);
insertMin(&h, 50); insertMin(&h, 20); insertMin(&h, 80);
insertMin(&h, 10); insertMin(&h, 60);
printf("Min: %d\n", h.data[0]); /* 10 */
printf("Extract: %d\n", extractMin(&h)); /* 10 */
printf("Extract: %d\n", extractMin(&h)); /* 20 */
printf("Extract: %d\n", extractMin(&h)); /* 50 */
return 0;
}
// Section 8
Priority Queue Using a Heap
In Unit 07 we built a priority queue using a simple array that searched for the highest priority element in O(n). A heap-based priority queue does all the same things in O(log n) — dramatically faster at scale. This is the real-world implementation used in every production system.
| Operation | Array-based (Unit 07) | Heap-based | Why better |
|---|
| Insert | O(1) | O(log n) | Heap: always maintains order |
| Get highest priority | O(n) | O(1) | Heap: root is always max/min |
| Remove highest priority | O(n) | O(log n) | Heap: heapify restores order |
| Build from n items | O(n) | O(n) | Both same — heap is faster after |
Real systems that use heap-based priority queues:
⚙️CPU Process Scheduling
The OS picks the highest-priority process to run next. A min-heap of process priorities makes this O(log n).
🗺️Dijkstra's Shortest Path
Always processes the nearest unvisited node first. A min-heap of distances makes each step O(log n) instead of O(n).
🏥Hospital Emergency Room
Critical patients are seen first. A max-heap of severity scores ensures the most urgent case is always at the front.
📦Event-Driven Simulation
Events are processed in time order. A min-heap of timestamps gives the next event in O(log n).
// Errors You Will Hit
Common Heap Mistakes
⚠ Wrong parent/child index formula
Symptom: Heap property violated after every operation — wrong elements being compared
Fix: For 0-indexed array: parent = (i-1)/2, left = 2i+1, right = 2i+2. For 1-indexed: parent = i/2, left = 2i, right = 2i+1. Be consistent throughout.
⚠ Not checking bounds before accessing children
Symptom: Accessing arr[left] or arr[right] when index is beyond heap size — reading garbage
Fix: Always check left < h->size and right < h->size before accessing children in heapifyDown.
⚠ Forgetting to update h->size on extract
Symptom: Extracted element remains accessible and heap size appears unchanged
Fix: After extract: h->size-- to shrink the heap. The last element is now logically outside the heap even though it remains in the array.
// Quick Reference
All Heap Operations
| Operation | Time | How it works |
|---|
| Peek max/min | O(1) | Read arr[0] — root is always max or min |
| Insert | O(log n) | Add at end, bubble up while out of order |
| Extract max/min | O(log n) | Move last to root, heapify down |
| Build heap | O(n) | Heapify down from last non-leaf to root |
| Heap sort | O(n log n) | Build heap + n extractions |
| Search | O(n) | No ordering between siblings — must scan all |
// What's Next
You Are Ready for Unit 14
You now understand heaps completely — the heap property, the array representation, insert with bubble-up, extract with heapify-down, build heap in O(n), heap sort, and why heaps are the foundation of every production priority queue.
In Unit 14 we cover Hashing — the technique behind O(1) lookup. Hash tables power database indexes, caches, language runtimes, and almost every fast system you have ever used. We build one from scratch in C and understand every design decision.
UP NEXT → UNIT 14
Hashing — O(1) Lookup
Hash functions, collisions, chaining, open addressing — built in C.
🎯 Key Takeaways
- ✓A heap is a complete binary tree with the heap property: max-heap = parent ≥ children, min-heap = parent ≤ children
- ✓A complete binary tree is always balanced — height is O(log n) guaranteed, no skewing possible
- ✓Heap stored as array: parent(i) = (i-1)/2, left(i) = 2i+1, right(i) = 2i+2
- ✓Insert: add at end, bubble up while larger than parent — O(log n)
- ✓Extract max/min: move last element to root, heapify down swapping with larger child — O(log n)
- ✓Peek at max/min: just read arr[0] — always O(1)
- ✓Build heap from unsorted array: heapify down from last non-leaf to root — O(n) total
- ✓Heap sort: build heap O(n) + n extractions O(n log n) = O(n log n) total, O(1) space
- ✓Heap-based priority queue: O(log n) insert and extract vs O(n) for naive array implementation
- ✓Heap does NOT support efficient search — siblings have no ordering, must scan all nodes O(n)