Don't memorize the heap — watch values sift up and down. A binary heap is a complete tree where every parent beats its children, so the maximum is always the root. It needs no pointers: it lives in a plain array where node i has children at 2i+1 and 2i+2. Push appends a value and sifts it up; pop takes the root and sifts the gap down. Both in O(log n) — the engine behind priority queues, Dijkstra, and heapsort.
parent ≥ children · max at the root · push sifts up · pop sifts down
HEAP
A complete binary tree with the heap property: every parent outranks its children. Max at the root.
ARRAY-BACKED
No pointers: node i has parent (i−1)/2, children 2i+1 and 2i+2.
PUSH
Append at the end, then sift up: swap with the parent while bigger.
POP
Take the root, move the last leaf up, then sift down past the bigger child.
heap.sim — max-heap · push 10, then pop the max
Ready
The same heap drawn two ways: a tree above, its array below. Every parent is ≥ its children, so the max sits at the root. Press Step to push 10 (sift up), then pop the max (sift down).
node i · parent (i−1)/2 · children 2i+1, 2i+2
9
Max (root)
7
Size
Weak order, strong speed
A heap makes a deliberate trade. It does not fully sort its elements — it only guarantees that each parent outranks its two children. That weak promise is exactly enough to keep the maximum pinned at the root, reachable in O(1), while costing only O(log n) to insert or remove. And because the tree is always complete — every level full except possibly the last, filled left to right — it maps perfectly onto an array with no wasted slots and no pointers. Index arithmetic replaces links: parent at (i−1)/2, children at 2i+1 and 2i+2. Every operation is a short walk along one root-to-leaf path, swapping as it goes.
01
Shape and order
Complete tree (filled left to right) plus the heap property (parent ≥ children). The shape lets it pack into an array.
02
Push = append + sift up
Put the value in the next slot, then swap it upward while it beats its parent. At most the tree height.
03
Pop = root out + sift down
The root is the max. Move the last leaf into the root, shrink, then swap down with the larger child.
04
Peek and build
Peek the max in O(1) — it is a[0]. Heapify an unsorted array bottom-up in O(n).
Peek max
O(1)
Push / pop
O(log n)
Build heap
O(n)
Space
O(n)
This one structure is a priority queue: always serve the best element next. Flip the comparison and it becomes a min-heap. It is the beating heart of Dijkstra and Prim (pull the cheapest edge), of heapsort (pop the max n times), of event simulations and task schedulers, and of top-k selection. Whenever you catch yourself repeatedly asking for the largest or smallest thing in a changing set, reach for a heap.
SOLVE IT YOURSELF
Solve it: heap sort
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement heap_sort(nums) using a binary max-heap (no built-in sort). First heapify the array so every parent beats its children, then repeatedly swap the root (the max) to the end and sift the new root down over the shrinking heap. Return the sorted list. O(n log n), in place.
HINTS — 4 IDEAS
In an array heap, node i has children 2i+1 and 2i+2. A sift-down swaps a node with its larger child until it is bigger than both.
Build the heap bottom-up: sift-down every node from index n//2 − 1 down to 0.
Now the max is at index 0. Swap it with the last slot, shrink the heap by one, and sift the new root down.
Repeat until the heap is empty — the array is left sorted ascending.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · In a max-heap, where is the maximum element?
The heap property forces every parent above its children, so the maximum bubbles all the way to the root and is readable in O(1).
2 · For node i in the array, where are its children?
A complete tree maps to an array by these index formulas; the parent of i is (i−1)/2. No pointers needed.
3 · After popping the root, how is the heap restored?
Promoting the last leaf keeps the tree complete; sifting it down against the larger child restores the heap property in O(log n).
Questions
Heap vs binary search tree?
A heap enforces only a weak parent-child order, giving O(1) access to the extreme but no efficient search and no sorted traversal. A BST maintains a full ordering: O(log n) search and an in-order walk that is sorted, but no O(1) min/max. Heaps for priority queues, BSTs for ordered lookups.
Is a priority queue the same as a heap?
A priority queue is the abstract idea — push, peek-best, pop-best. A binary heap is its usual implementation. Other implementations exist (pairing heaps, Fibonacci heaps), but the array-backed binary heap is the workhorse for Dijkstra, Prim, heapsort and top-k.
How do I get a min-heap?
Flip the comparison: keep every parent less than or equal to its children, so the minimum sits at the root. Every operation is identical with the inequality reversed — or just store negated keys in a max-heap.
Two short walks along one path.
Push appends and sifts up; pop promotes the last leaf and sifts down. A weak order, and the best element is always one lookup away.