loading
loading
loading
loading
A complete binary tree, stored flat in an array, that keeps the smallest (or largest) element one O(log n) extraction away — the standard way to build a priority queue.
A binary heap is a complete binary tree — every level filled left to right before the next begins — which means it can be stored as a plain array with no pointers: a node at index i has children at 2i+1 and 2i+2, and a parent at ⌊(i−1)/2⌋. The heap property (a min-heap's parent is always ≤ its children; a max-heap's parent is always ≥) is weaker than a BST's ordering invariant — it only constrains parent-child pairs, not left-vs-right — which is exactly why insert and extract are both O(log n) instead of needing a full rebalance. A priority queue is the abstract interface (insert, peek-highest-priority, extract-highest-priority); a binary heap is the concrete data structure that implements it efficiently.
Step through heaps & priority queues live, one move at a time — this becomes a fully interactive visualizer.
Coming soonfunction extractMax(heap) {
const max = heap[0];
const last = heap.pop(); // shrink first
if (heap.length === 0) return max;
heap[0] = last; // move last element to the root
let i = 0;
while (true) {
const left = 2 * i + 1, right = 2 * i + 2;
let largest = i;
if (left < heap.length && heap[left] > heap[largest]) largest = left;
if (right < heap.length && heap[right] > heap[largest]) largest = right;
if (largest === i) break; // heap property restored
[heap[i], heap[largest]] = [heap[largest], heap[i]];
i = largest; // continue sifting down
}
return max;
}function insert(heap, value) {
heap.push(value); // append — keeps the tree complete
let i = heap.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (heap[parent] >= heap[i]) break; // heap property holds — done
[heap[parent], heap[i]] = [heap[i], heap[parent]];
i = parent; // continue sifting up
}
}// Keep a MIN-heap of size k. Any new value larger than the heap's
// smallest (the root) replaces it — after scanning n elements, the
// heap holds exactly the k largest, in O(n log k) instead of O(n log n).
function topK(nums, k) {
const heap = nums.slice(0, k);
buildMinHeap(heap);
for (let i = k; i < nums.length; i++) {
if (nums[i] > heap[0]) {
heap[0] = nums[i];
siftDown(heap, 0);
}
}
return heap;
}| Binary Heap | Binary Search Tree (balanced) | |
|---|---|---|
| Ordering guarantee | Parent vs children only | Left < node < right, everywhere |
| Find the min/max | O(1) — always the root (min-heap/max-heap) | O(log n) — walk to a leaf |
| Insert | O(log n) | O(log n) |
| Search for an arbitrary value | O(n) — no ordering to search by | O(log n) |
| Sorted iteration | Not supported directly | O(n) in-order traversal |
| Storage | Flat array, no pointers | Nodes with left/right pointers |
| Typical use | Priority queues, top-K, scheduling | Ordered maps/sets, range queries |
They optimize for different questions. A BST's invariant (left < node < right, everywhere) makes it good at 'find this specific value' and 'give me everything in sorted order.' A heap's weaker invariant (parent vs children only) throws away the ability to search efficiently — but in exchange, it can find the min or max in O(1) instead of O(log n), and both insert and extract stay O(log n) with a much simpler, pointer-free array implementation. Reach for a heap when the only question you ever ask is 'what's the highest/lowest priority item right now?' — not 'is X in here?'
Sifting a node down costs time proportional to its height in the tree, and a complete binary tree is bottom-heavy: roughly half the nodes are leaves (height 0, free), a quarter are one level up (height 1), an eighth are two levels up, and so on. Summing height × node-count across every level converges to O(n) total work, not O(n log n) — even though any single sift-down can cost up to O(log n). This is the mathematical reason 'heapify the whole input, then extract n times' (heap sort) beats 'insert n times one at a time' for building a heap from scratch.
A priority queue is the abstraction that shows up everywhere scheduling or 'do the most urgent thing next' matters: OS task schedulers, event-driven simulations processing events in timestamp order, and Dijkstra's algorithm and A* search, both of which repeatedly need 'the unvisited node with the smallest known distance' — exactly a min-heap extract-min, run once per node.
To find the k largest elements among n, don't sort everything (O(n log n)). Keep a *min-heap* of size k: scan the input once, and for every element larger than the heap's current minimum (its root), swap it in and sift down. Only elements that make the current top-k ever cost a heap operation, so this runs in O(n log k) — a real asymptotic win when k is much smaller than n. The same pattern, with the heap type flipped, finds the k smallest.
Heap sort builds a max-heap from the whole array in O(n), then repeatedly swaps the root (the current maximum) with the last element of the still-active heap and sifts the new root down — the exact extract-max operation described above, run n times, with the 'popped' slot reused as storage for the growing sorted tail instead of a separate output array. That reuse is what gives heap sort its O(1) auxiliary space, and it's also why it isn't stable: sifting swaps purely on value, with no memory of which equal element came first. See the Heap Sort Visualizer for this running step by step, showing the tree and its backing array at the same time.
State the property you need (min or max) before coding — mixing them up is the most common heap bug. Know the Top-K-via-bounded-heap pattern by name; it's asked constantly and its O(n log k) bound is the whole point of the answer. Be ready to name a 'heap vs BST' tradeoff on request: a heap wins when you only ever need the extreme value; a BST wins the moment you need search or sorted iteration. And know that most languages' standard library exposes a heap as a 'priority queue,' not a 'heap' — the interface name, not the structure name, is usually what you'll actually reach for.
No — priority queue is the abstract interface (insert an item with a priority, get back the highest-priority one). A binary heap is the standard concrete data structure used to implement that interface efficiently; some languages' 'PriorityQueue' class is a heap under the hood.
Heap sort is literally 'build a max-heap, then extract the max n times' — the interactive Heap Sort Visualizer shows this exact insert/extract-max machinery running step by step, on both a tree view and the underlying array.
When the only operation you need is 'give me the current min or max,' repeatedly, with efficient inserts in between — a heap does this with a simpler, pointer-free array and O(1) peek. Once you need search-by-value or sorted iteration, a BST is the right tool; a heap can't do either efficiently.
Removing the root directly would leave two orphaned subtrees with no way to merge them back into one tree in O(log n). Moving the last element into the root's slot keeps the tree complete (still a valid array-backed shape) at zero cost, and a single sift-down is enough to restore the heap property from there.
Share what clicked for you and see notes from other learners on this topic.
Coming soon