Heap Overview
Understanding Priority Queues and Binary Heaps.
What is a Heap?
A Heap is a specialized tree-based data structure that satisfies the Heap Property:
- Min-Heap: The value of each node is less than or equal to the values of its children. The root is the minimum.
- Max-Heap: The value of each node is greater than or equal to the values of its children. The root is the maximum.
It is commonly used to implement a Priority Queue.
The Motivation: Fast Access to Extremes
Imagine you need to constantly retrieve the highest priority task from a dynamic list of tasks. You add new tasks (insert) and complete the highest priority one (extract max).
A standard Array or List is inefficient:
- Unsorted Array: Insert O(1), Get Max O(N).
- Sorted Array: Get Max O(1), Insert O(N).
We need a structure that balances these. A Heap does both in O(log N).
Why not just Sort?
If you keep the array sorted, finding the max is fast (O(1)). But adding a new element requires shifting everyone else, costing O(N). If you have N insertions, that's O(N²). A Heap manages this dynamically in O(N log N) total for N insertions.
When should I use a Heap?
Top K Elements: Finding the K largest/smallest items (e.g., "Trending Topics").
Merge K Sorted: Merging multiple sorted streams efficiently.
Scheduling: Processing tasks by priority (e.g., OS Scheduler).
Shortest Path: Dijkstra's Algorithm uses a Min-Heap.
The Intuition: Bubbling Up & Down
A Heap is usually a Complete Binary Tree.
- Insert: Add to the bottom-right, then "bubble up" (swap with parent) until heap property is restored.
- Extract: Remove root, move the last element to the root, then "bubble down" (swap with smaller child) until restored.
Because the tree height is log(N), these operations are fast.
Interactive Walkthrough
EVERY PARENT ≤ ITS CHILDREN
EMPTY HEAP
operations
empty heap
heap array
Size
0
Min
—
returned
Nothing returned yet
An empty min-heap: every parent will be at most its children, so the minimum sits at heap[0]
Next
push 5: the heap was empty, so it goes in slot 0
Ops
Legend & Complexity
The value moving, or the root being read
The parent or child it was compared with
peek or pop on an empty heap
push / pop
O(log n)
peek
O(1)
Space
O(n)
Run push, peek and pop on a min-heap. The tree and the array under it are the same heap: a push appends and sifts up, a pop reads the root, moves the last value into it and sifts down. Try Pop from empty to see why code checks the size first.
Dry Run Table (Min-Heap Insert)
Operations: push 5, push 3, push 8, push 1, pop, peek
| Step | Operation | Array after | What happened |
|---|---|---|---|
| 1 | push 5 | [5] |
5 is the root |
| 2 | push 3 | [3, 5] |
3 < its parent 5: swap up to the root |
| 3 | push 8 | [3, 5, 8] |
Its parent 3 is not larger: it stays |
| 4 | push 1 | [1, 3, 8, 5] |
1 < 5: swap to slot 1; 1 < 3: swap to the root |
| 5 | pop → 1 | [3, 5, 8] |
The last value 5 moves to the root; its smaller child 3 < 5: swap |
| 6 | peek → 3 | [3, 5, 8] |
The root is the minimum |
The Solution Template
A min-heap stored in an array, in every language: push sifts up, pop sifts down, peek reads the root. Slot i has its parent at (i - 1) / 2 and its children at 2i + 1 and 2i + 2.
Heap Overview Code
1class MinHeap {2 constructor() {3 this.heap = [];4 }56 push(val) {7 const h = this.heap;8 h.push(val);9 let i = h.length - 1;10 while (i > 0 && h[(i - 1) >> 1] > h[i]) {11 const parent = (i - 1) >> 1;12 [h[i], h[parent]] = [h[parent], h[i]];13 i = parent;14 }15 }1617 peek() {18 return this.heap[0];19 }2021 pop() {22 const h = this.heap;23 const top = h[0];24 const last = h.pop();25 if (h.length > 0) {26 h[0] = last;27 let i = 0;28 while (true) {29 const left = 2 * i + 1, right = 2 * i + 2;30 let smallest = i;31 if (left < h.length && h[left] < h[smallest]) smallest = left;32 if (right < h.length && h[right] < h[smallest]) smallest = right;33 if (smallest === i) break;34 [h[i], h[smallest]] = [h[smallest], h[i]];35 i = smallest;36 }37 }38 return top;39 }40}
Edge Cases & Common Mistakes
- Empty heap:
heap[0]does not exist, sopeekandpopmust check the size first. - Min vs max: Python's
heapqand Java'sPriorityQueueare min-heaps; C++'spriority_queueis a max-heap unless givengreater<int>. To get a max-heap from a min-heap, push negated values. - Equal values: sift up and sift down compare strictly, so equal values never swap — and the heap is still valid.
- Changing a value already in the heap: nothing reorders it. Remove it and push it again, or sift from its slot.
Summary
- Use a heap for fast access to the minimum or maximum, not for searching.
- To keep the k largest values, use a min-heap of size k and evict its minimum; to keep the k smallest, use a max-heap of size k.
- push and pop are O(log n) and peek is O(1), against O(n) inserts for a sorted array.