Binary Heaps & Priority Queues
What is a Binary Heap?
A binary heap is a complete binary tree that satisfies the heap property:
- Min-Heap: Every parent ≤ its children. The root is the minimum.
- Max-Heap: Every parent ≥ its children. The root is the maximum.
Heaps are stored as arrays: for node at index i, its left child is at 2i+1, right child at 2i+2, and parent at ⌊(i-1)/2⌋.
Insertion (Bubble Up)
Insert at the end of the array, then bubble up: compare with parent, swap if violating heap property. Repeat until the heap property is restored.
heap.push(value) i = heap.length - 1 while i > 0: parent = floor((i - 1) / 2) if heap[i] < heap[parent]: swap(heap[i], heap[parent]) i = parent else: break
▶ Heap Insert Animation (Bubble Up)
Watch value 2 being inserted and bubbling up to maintain min-heap property. Arrows show swap direction.
Extract Min (Bubble Down)
Remove the root (minimum), move the last element to root, then bubble down: swap with the smaller child until the heap property is restored.
min = heap[0] heap[0] = heap.pop() // move last to root i = 0 while true: smallest = i left = 2*i + 1, right = 2*i + 2 if left < len and heap[left] < heap[smallest]: smallest = left if right < len and heap[right] < heap[smallest]: smallest = right if smallest == i: break swap(heap[i], heap[smallest]) i = smallest return min
▶ Extract-Min Animation (Bubble Down)
Watch the root removed and the last element bubbling down with arrows showing comparisons.
Build Heap (Heapify)
Given an unsorted array, build a heap in O(n) by calling bubbleDown on every non-leaf, starting from the last internal node up to the root.
for i = floor(n/2) - 1 down to 0: bubbleDown(arr, i)
▶ Build Heap Animation
Watch an unsorted array [15, 10, 8, 12, 3, 9, 5] get transformed into a valid min-heap.
Complexity
| Operation | Time | Description |
|---|---|---|
| Insert | O(log n) | Bubble up at most height levels |
| Extract-Min/Max | O(log n) | Bubble down at most height levels |
| Peek (get min/max) | O(1) | Root is always min/max |
| Build Heap | O(n) | Bottom-up heapify |
| Heap Sort | O(n log n) | Build + n extractions |
C++ Implementation
#include <vector>
#include <algorithm>
class MinHeap {
std::vector<int> data;
void bubbleUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (data[i] < data[parent]) {
std::swap(data[i], data[parent]);
i = parent;
} else break;
}
}
void bubbleDown(int i) {
int n = data.size();
while (true) {
int smallest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < n && data[left] < data[smallest]) smallest = left;
if (right < n && data[right] < data[smallest]) smallest = right;
if (smallest == i) break;
std::swap(data[i], data[smallest]);
i = smallest;
}
}
public:
void insert(int val) {
data.push_back(val);
bubbleUp(data.size() - 1);
}
int extractMin() {
int min = data[0];
data[0] = data.back();
data.pop_back();
if (!data.empty()) bubbleDown(0);
return min;
}
int peek() const { return data[0]; }
bool empty() const { return data.empty(); }
int size() const { return data.size(); }
// Build heap from array in O(n)
static MinHeap buildHeap(std::vector<int> arr) {
MinHeap h;
h.data = std::move(arr);
for (int i = h.data.size() / 2 - 1; i >= 0; --i)
h.bubbleDown(i);
return h;
}
};Applications
- Priority Queues, scheduling, Dijkstra’s & Prim’s algorithms.
- Heap Sort, in-place O(n log n) sorting.
- Top-K problems, maintain a heap of size K for streaming data.
- Merge K sorted lists, use min-heap to always process the smallest element.
- Median maintenance, two heaps (max-heap + min-heap) for running median.
Summary
- Binary heaps are complete binary trees stored as arrays.
- Insert = add at end + bubble up. Extract = remove root + bubble down.
- Build heap runs in O(n) using bottom-up heapify.
- Fundamental for priority queues, sorting, and graph algorithms.