Heaps

The Efficient Priority Queue

Use arrow keys or buttons to navigate

What is a Heap?

A complete binary tree with a special ordering property

Two Requirements

  • Complete binary tree — every level fully filled except the last, which fills left to right
  • Heap-order property — every node satisfies an ordering rule relative to its children

Interactive: Is This a Valid Min-Heap?

Min-Heap vs Max-Heap

Key Idea

A heap is not a fully sorted structure. It only guarantees the root is the min (or max). Left child is not necessarily smaller than right child. This partial ordering is what makes heaps fast.

Analogy: Company Hierarchy

The CEO (root) always has the lowest employee ID. Every manager's ID is lower than their reports. Finding the CEO is instant — just look at the top!

Heap Properties

The three properties that make heaps work

1. Complete Binary Tree

All levels full except possibly the last, filled left to right.

2. Heap-Order Property

Min-heap: parent ≤ children
Max-heap: parent ≥ children

3. Height = O(log n)

Complete tree → always balanced → height = floor(log₂ n).

Key Idea

Every operation that travels root-to-leaf (or vice versa) costs at most O(log n). With n = 1,000,000, that's only ~20 steps instead of 1,000,000.

Why Heaps Are Brilliant

The best of both worlds for priority queue operations

The PQ Problem

ImplementationinsertremoveMin
Unsorted ListO(1)O(n)
Sorted ListO(n)O(1)
HeapO(log n)O(log n)

Key Idea

A heap gives O(log n) for both operations. With n = 1,000,000, that's ~20 steps instead of 1,000,000. This makes heaps the go-to PQ implementation.

How?

insert: add at bottom, bubble UP → O(log n)
removeMin: swap root with last, bubble DOWN → O(log n)
Both travel at most the height of the tree.

Array Representation

No pointers needed — store a heap in a simple array!

Interactive: Tree ↔ Array

Hover over any node or array cell to highlight both

Level-Order = Array Order

Because the tree is complete, there are no gaps when we lay it out level by level. A flat array with zero wasted space — no left/right child pointers needed!

Level-by-Level Mapping

Level 0: 1 → arr[0] = 1
Level 1: 3, 5 → arr[1]=3, arr[2]=5
Level 2: 7, 9, 6 → arr[3]=7, arr[4]=9, arr[5]=6

Analogy: Stadium Seating

Fill seats row by row, left to right, no empty seats. Seat number alone tells you the row and position — exactly how a heap fits in an array.

Array Indexing Formulas

Navigate the tree using simple arithmetic — no pointers!

The Three Formulas (0-indexed)

parent(i) = (i - 1) / 2
leftChild(i) = 2 * i + 1
rightChild(i) = 2 * i + 2

Interactive Calculator

Visualized on the Tree

Watch Out: Integer Division

Parent uses integer division (floor). Both index 1 and 2 map to parent 0: (1-1)/2 = 0 and (2-1)/2 = 0.

Insert: Upheap (Bubble Up)

Add at the end, then swim the element up to restore heap order

Interactive Insert Playground

Algorithm

  1. Add new element at the end (next leaf spot)
  2. Compare with parent
  3. If new element < parent, swap
  4. Repeat until heap order restored or we reach root
insert(heap, value):
heap.add(value) // add at end
i = heap.size - 1
while i > 0:
parent = (i - 1) / 2
if heap[i] < heap[parent]:
swap(heap[i], heap[parent])
i = parent
else: break

Time: O(log n)

Worst case: bubble all the way to root. Distance = height = O(log n). Each swap is O(1).

Analogy: New Employee

Joins at the bottom. If they outrank their manager (smaller key), they swap. Keep promoting until they meet someone who outranks them.

Insert Example: Insert 2 into a Min-Heap

Step-by-step trace with code sync

Code with Highlights

heap.add(2); // add at end, idx=6
i = 6;
// compare heap[i] with heap[parent]
// if heap[i] < heap[parent]: SWAP
// else: BREAK — done!

Result

Element 2 bubbled up one level. Only 1 swap because 2 > 1 (the root). Worst case: an element could bubble all the way to root — O(log n) swaps.

Completeness Preserved

Adding at the end always keeps the tree complete. The bubble-up only affects the order, never the shape.

RemoveMin: Downheap (Bubble Down)

Remove root, move last to root, then sink it down

Interactive RemoveMin

Algorithm

  1. Save root value (the min)
  2. Move last element to root
  3. Remove last position (shrink)
  4. Bubble down: swap with smaller child
  5. Repeat until heap order restored
removeMin(heap):
min = heap[0]
heap[0] = heap[last]
heap.removeLast()
i = 0
while hasLeftChild(i):
smallest = smallerChild(i)
if heap[i] > heap[smallest]:
swap(heap[i], heap[smallest])
i = smallest
else: break
return min

Why the Smaller Child?

Swapping with the larger child would make it the parent of the smaller child — violating heap order! Always pick the smaller child in a min-heap.

RemoveMin Example

Step-by-step trace of removing the minimum

Why Move Last to Root?

Key Idea

Moving the last element to root preserves completeness. Bubble-down restores heap order. Two properties, two steps, O(log n).

Analogy: CEO Leaves

The CEO retires. The most junior employee is temporarily placed at the top. They then get demoted level by level until they find their proper rank.

Building a Heap: Top-Down

Insert elements one at a time — O(n log n)

Step-Through: Build from [5, 3, 8, 1, 4]

Complexity: O(n log n)

Each insert is O(log n) worst case. Doing n inserts → O(n log n) total.

Can We Do Better?

Yes! The bottom-up approach builds a heap in O(n). The key insight: start from the leaves and sift down, not from the root and sift up.

// Top-down build
for (int x : input)
heap.insert(x); // O(log n) each
// Total: O(n log n)

The Problem

Later inserts (when the heap is big) bubble up a long distance. Most of the work happens when it's most expensive.

Building a Heap: Bottom-Up (Heapify)

Start from the last internal node and sift down — O(n)!

Interactive Heapify

Algorithm

heapify(arr):
// skip leaves — they're trivial heaps
for i = (n/2 - 1) down to 0:
siftDown(arr, i)

Process from the last internal node up to root. Each node sifts down at most to the bottom.

Key Idea

Leaves (half the nodes) do zero work. A quarter sift 1 level. Only the root sifts h levels. The work is concentrated where it's cheapest!

Why Bottom-Up Heapify is O(n)

Most nodes are near the bottom and barely need to move

The Math

The Intuition

n/2 leaves → sift 0 levels (skip!)

n/4 nodes → sift at most 1 level

n/8 nodes → sift at most 2 levels

...

1 node (root) → sift at most h levels

Key Comparison

Top-down = O(n log n) — the many late inserts bubble up a long distance.
Bottom-up = O(n) — the many bottom nodes sift a short distance. Work is concentrated where it's cheapest.

Analogy

Top-down: training each new employee from scratch. Bottom-up: reorganizing an existing company — most people barely move, only the top executives shuffle significantly.

Heap Sort

Build a max-heap, then repeatedly extract the maximum — O(n log n), in-place!

Interactive Heap Sort

Algorithm

  1. Build max-heap (bottom-up) — O(n)
  2. Repeat n-1 times:
    • Swap root (max) with last unsorted element
    • Shrink heap by 1
    • Sift down new root
heapSort(arr):
buildMaxHeap(arr) // O(n)
for i = n-1 down to 1:
swap(arr[0], arr[i]) // max → end
heapSize--
siftDown(arr, 0) // O(log n)

Why Max-Heap?

We want ascending order. Extract max and place at end → sorted region grows right-to-left. Heap shrinks, sorted part grows.

Properties

Time: O(n log n) always
Space: O(1) — in-place!
Stable: No
Quicksort is faster in practice but O(n²) worst case. Merge sort is stable but needs O(n) extra space.

Heap Sort Trace

Sort [5, 3, 8, 1, 4, 2] step by step using max-heap extraction

Heap Sort = Build Max-Heap + Repeated Extract-Max

Each extract-max places the largest remaining element at the end. The sorted region grows from right to left. Total: O(n log n), in-place, not stable.

Min-Heap vs Max-Heap

Same structure, just flip the comparison operator

Min-Heap

  • Parent ≤ children
  • Root = smallest element
  • Used for: priority queues, Top-K, Dijkstra
  • removeMin() returns smallest

Java's PriorityQueue = min-heap by default

Max-Heap

  • Parent ≥ children
  • Root = largest element
  • Used for: heap sort, scheduling
  • removeMax() returns largest

Use Collections.reverseOrder() comparator

Key Idea

The only difference is the direction of the comparison. All algorithms (insert, remove, heapify) are structurally identical — just swap < with >. Think of them as the same data structure with a configurable comparator.

Challenge: Trace Heap Operations

Predict the state after a sequence of operations

Starting with an empty min-heap, perform these operations:

1. insert(5)
2. insert(3)
3. insert(8)
4. insert(1)
5. removeMin()
6. insert(2)
7. removeMin()

What is the array representation of the heap after all operations?

Java's PriorityQueue

Built-in min-heap — ready to use

Basic Usage (Min-Heap)

PriorityQueue<Integer> pq =
new PriorityQueue<>();
pq.add(5); // insert 5
pq.add(3); // insert 3
pq.add(8); // insert 8
pq.add(1); // insert 1
pq.peek(); // → 1 (min, no remove)
pq.poll(); // → 1 (remove min)
pq.poll(); // → 3
pq.poll(); // → 5
pq.poll(); // → 8
MethodDescriptionTime
add(e)InsertO(log n)
peek()View minO(1)
poll()Remove minO(log n)
size()CountO(1)

Max-Heap with Reversed Comparator

// Option 1: Collections.reverseOrder()
PriorityQueue<Integer> maxPQ =
new PriorityQueue<>(
Collections.reverseOrder()
);
// Option 2: Lambda comparator
PriorityQueue<Integer> maxPQ2 =
new PriorityQueue<>((a, b) -> b - a);

Custom Objects

// By task priority
PriorityQueue<Task> taskPQ =
new PriorityQueue<>(
(t1, t2) -> t1.priority - t2.priority
);

Common Mistake

Java's PriorityQueue is a min-heap by default. If you need the largest first, you must provide a reversed comparator!

Challenge: Fix the Bug

This bottom-up heapify has a subtle bug. Can you spot it?

void buildMinHeap(int[] arr) {
int n = arr.length;
for (int i = n / 2; i >= 0; i--) {
siftDown(arr, i, n);
}
}
void siftDown(int[] a, int i, int n) {
while (true) {
int smallest = i;
int l = 2*i + 1, r = 2*i + 2;
if (l < n && a[l] < a[smallest])
smallest = l;
if (r < n && a[r] < a[smallest])
smallest = r;
if (smallest == i) break;
swap(a, i, smallest);
i = smallest;
}
}

Application: Top-K Elements

Find the k largest elements using a min-heap of size k

The Trick: Min-Heap as Gatekeeper

PriorityQueue<Integer> minHeap =
new PriorityQueue<>();
for (int num : stream) {
if (minHeap.size() < k) {
minHeap.add(num);
} else if (num > minHeap.peek()) {
minHeap.poll(); // evict smallest
minHeap.add(num);
}
}

Time: O(n log k)

Process n elements, each heap op is O(log k). For k=10 and n=1 billion, that's ~33 ops per element instead of sorting everything. The heap root always holds the smallest of the k largest — the gatekeeper.

Challenge: Pick the Right Heap

Min-heap or max-heap? Match each scenario to the correct choice.

1. Find the 3 smallest elements in a stream of 1 million numbers.

2. Find the 5 largest elements in a stream.

3. Sort an array in ascending order using heap sort.

4. Implement a task scheduler where lowest priority number = highest urgency.

Application: Merge K Sorted Lists

Use a min-heap of size k to efficiently merge — O(n log k)

Algorithm

  1. Insert first element of each list into min-heap (tagged with list index)
  2. Extract min → add to result
  3. Insert next element from that same list
  4. Repeat until heap is empty

Analogy

Like a tournament bracket for k runners. Pick the fastest (min), record their time, and their next teammate enters. The heap keeps the bracket organized.

Summary & Cheat Sheet

Everything you need to know about heaps in one slide

Core Operations

Array Formulas (0-indexed)

parent(i) = (i - 1) / 2
leftChild(i) = 2 * i + 1
rightChild(i) = 2 * i + 2

When to Use a Heap

  • Priority Queue — process items by priority
  • Top-K elements — min-heap of size k, O(n log k)
  • Merge K sorted lists — min-heap of size k
  • Heap Sort — O(n log n), in-place, not stable
  • Median finding — two heaps (max + min)
  • Dijkstra's algorithm — shortest path

Heap Sort Properties

Time: O(n log n) — always
Space: O(1) — in-place!
Stable: NO
vs Merge Sort: stable but O(n) space
vs QuickSort: O(n²) worst case

The Big Picture

A heap is a partially ordered, complete binary tree stored in an array. It trades full sorting for fast access to the extreme element.

Quiz: Test Your Heap Knowledge

3 questions — pick the best answer

Q1: What is the time complexity of building a heap using bottom-up heapify?

Q2: In a max-heap with array [9, 7, 8, 3, 5], what is the left child of index 1?

Q3: To find the top-5 largest from a billion numbers, which heap do you use?

Quiz: Predict removeMin Steps

Given a min-heap, trace the downheap after removeMin

Min-heap array: [2, 5, 3, 8, 7, 6, 4]

After removeMin():

  1. Remove root (2), move last element (4) to root
  2. Array becomes: [4, 5, 3, 8, 7, 6]
  3. Downheap from root...

What is the final array after downheap?

Quiz: Predict the Output

What does this Java code print?

PriorityQueue<Integer> pq =
new PriorityQueue<>();
int[] data = {7, 2, 9, 4, 1, 5};
for (int x : data) pq.add(x);
pq.poll(); // remove first min
pq.poll(); // remove second min
pq.add(3);
System.out.println(pq.peek());
System.out.println(pq.size());

Enter your predictions: