Start here: the problem it solves#
TL;DRthe 30-second version
- A priority queue is a bag of items where you repeatedly pull out the smallest (or largest). The naive ways are all O(n) on one side: a sorted array is slow to insert into; an unsorted array is slow to find the minimum in.
- A binary heap fixes both. It only enforces that every parent is smaller than its children (a min-heap), so the smallest item is always at the root — O(1) to read.
- The tree is complete (filled left to right), so it lives in a plain array with no pointers: the node at index i has children at 2i+1 and 2i+2 and a parent at (i−1)/2.
- Push adds the item at the end and sifts it up its ancestors; pop removes the root, moves the last leaf up top, and sifts it down. Each touches one root-to-leaf path, so both are O(log n). Building a heap from n items at once is O(n).
You're writing a scheduler. Thousands of tasks are waiting, each with a time it should run. Every moment you need the same answer: which task is due soonest? So the operation you do constantly is 'give me the smallest deadline', and alongside it you keep adding new tasks and removing ones you've run.
The obvious idea is to keep the tasks in a sorted array. Then the soonest task is just the first element, which is fast to read. But adding a new task means inserting it in the right place, and that shifts everything after it down by one slot. With 10,000 tasks that's up to 10,000 moves per insert. You do this constantly, so the shifting alone sinks you.
So you try the opposite: keep the tasks in an unsorted array. Now adding one is cheap, you just append it. But finding the soonest task means scanning all 10,000 every single time, because it could be anywhere. You've moved the O(n) cost from insert to find-min, and find-min is the thing you do most. Neither plain array wins, because each is fast on one operation and slow on the other.
Here's the insight that breaks the deadlock. You never actually need the tasks fully sorted. You only ever look at one of them: the smallest. Keeping all 10,000 in perfect order is doing far more work than the question requires. What if you kept them only loosely ordered, just ordered enough that the smallest is always easy to find, and cheap to restore after each change?
The mechanism: a tree with one weak rule#
Arrange the items as a binary tree and enforce a single rule: every parent is smaller than both of its children. That's it. This is called the heap property, and a tree that obeys it is a min-heap. (Flip the comparison and you get a max-heap, with the largest on top. Everything below works the same way.)
Notice what this rule does and does not give you. It does not sort the tree: two siblings can be in any order, and a node deep on the left can be smaller than one high on the right. But it forces the single smallest item to sit at the very top, the root, because the root is smaller than its children, which are smaller than theirs, all the way down. So reading the minimum is instant. You just look at the root.
every parent is smaller than its children; the smallest key, 1, sits at the root
- 1i=0
- 3i=1
- 5i=3
- 9i=4
- 6i=2
- 8i=5
- 7i=6
- 3i=1
The second design choice makes the whole thing cheap to store. We keep the tree complete, meaning every level is packed full except the bottom one, which fills in from the left. A complete tree has no gaps, so we can lay it out in a flat array in top-to-bottom, left-to-right order and never waste a slot. And once it's an array, we don't need child or parent pointers at all. Simple arithmetic on the index gives us the family of any node.
index: 0 1 2 3 4 5 6
value: 1 3 6 5 9 8 7
^root \ \
children of index i: left = 2i+1, right = 2i+2
parent of index i: (i - 1) / 2
index 0 (value 1) -> children at 1 and 2 (values 3, 6)
index 2 (value 6) -> children at 5 and 6 (values 8, 7)Now the operations. There are only two that change the heap, and both work the same way: make the change wherever it's cheap, which temporarily breaks the heap property in one spot, then walk that one broken spot back into place along a single path.
To push a new item, put it in the next free array slot, which is the next leaf on the bottom row. That keeps the tree complete. But the new item might be smaller than its parent, which breaks the rule. So you sift it up: compare it with its parent, and if it's smaller, swap them. Repeat with its new parent, and keep climbing until it meets a parent that's already smaller, or it reaches the root. The item bubbles up one single path from its leaf toward the root, and everything off that path is untouched.
To pop the minimum, take the root, since that's the answer. That leaves a hole at the top. Fill it by moving the last leaf, the final array element, up into the root and shrinking the array by one. The tree is complete again, but that leaf is probably far too big to be the root, which breaks the rule. So you sift it down: compare it with its two children, and if the smaller child is smaller than it, swap them. Repeat from its new position, always following the smaller child, until both children are bigger or you hit a leaf. Again the item travels one single path, this time from root toward a leaf.
That's the entire structure. A binary heap is a complete binary tree, stored as an array, kept just barely ordered by the parent-beats-children rule, with a push that sifts up and a pop that sifts down. When you use it to always serve the highest-priority item first, you're using it as a priority queue.
Walking a push and a pop#
Take the heap above, whose array is [1, 3, 6, 5, 9, 8, 7], and push the value 2.
- Append 2 at index 7, the next free slot. Its parent is at index (7−1)/2 = 3, which holds 5.
- Compare 2 with 5. 2 is smaller, so swap them. Now 2 is at index 3; its parent is at index (3−1)/2 = 1, which holds 3.
- Compare 2 with 3. Still smaller, so swap. Now 2 is at index 1; its parent is index 0, the root, holding 1.
- Compare 2 with 1. Not smaller, so stop. 2 has found its place just below the root. The push cost 2 swaps — the height of the tree, no more.
Now pop the minimum from the original heap [1, 3, 6, 5, 9, 8, 7].
- The root, 1, is the answer. Take it out, leaving a hole at index 0.
- Move the last element, 7 at index 6, into the root and shrink the array to length 6.
- Sift 7 down. Its children are 3 (index 1) and 6 (index 2). The smaller is 3, and 3 is smaller than 7, so swap. 7 is now at index 1.
- 7's children are now 5 (index 3) and 9 (index 4). The smaller is 5, and 5 is smaller than 7, so swap. 7 is now at index 3, a leaf. Stop. The heap is [3, 5, 6, 7, 9, 8], valid again, with the new minimum 3 on top.
Open the simulator to watch this happen live: push a small key and see it bubble up one path, then pop the root and watch the last leaf sink back down. The array view and the tree view show the same values, so you can see the index arithmetic line up with the tree positions step by step.
What it costs#
A binary heap is always perfectly balanced. Because it's a complete tree by construction, its height is exactly floor(log₂ n) with no rebalancing ever needed, unlike a search tree that has to rotate to stay short. That fixed height is what pins down every cost.
- Peek (read the min/max): O(1). It's always at the root, array index 0.
- Push: O(log n). One sift-up along a path no longer than the height.
- Pop: O(log n). One sift-down along a path no longer than the height.
- Build a heap from n items at once: O(n), not O(n log n). Sifting down from the bottom parents upward, most items are near the leaves and barely move, and the total work sums to linear.
- Space: O(n). Just the array of items; no pointers, no per-node overhead.
PredictYou keep 10,000 pending timers in a min-heap keyed by fire-time. Each tick you pop the ones that are due. Roughly how many comparisons does a single pop cost, and why isn't it close to 10,000?
Hint: How tall is a complete tree of 10,000 nodes, and how many comparisons does sift-down do per level?
About 25–30 comparisons, not 10,000. A complete tree of 10,000 nodes is only about log₂(10,000) ≈ 13 levels tall. Sift-down does roughly two comparisons per level (pick the smaller child, then compare it against the sinking value), so around 2 × 13 ≈ 26 comparisons. The heap never scans the other timers; it only walks one root-to-leaf path. That's the whole reason a scheduler can keep re-checking 'what's due next' cheaply.
Variants worth knowing
- d-ary heap — give each node d children instead of 2. A larger d makes the tree shorter, so pushes (which only compare with one parent per level) get faster, while pops get a little slower (they compare against d children per level). Go's runtime uses a 4-ary heap for its timers for exactly this balance, and it also improves cache behavior.
- Min-max heap — supports both extract-min and extract-max in O(log n) by alternating min-levels and max-levels. Useful when you need a double-ended priority queue.
- Indexed / addressable heap — keep a side map from item to its current array index. This is what lets you do decrease-key: change an item's priority and re-sift it in O(log n). Dijkstra's algorithm needs this to lower a vertex's tentative distance.
- Fibonacci and pairing heaps — fancier structures with a faster amortized decrease-key (O(1) amortized), which improves Dijkstra's and Prim's theoretical bounds. In practice their constants are high, so a plain binary heap usually wins on real inputs.
Common misconceptions & gotchas
Is a heap the same as a sorted list?
No, and this is the most common mistake. A heap is only partially ordered: the root is the extreme, but the rest is not sorted. Reading the array left to right gives you no meaningful order, and there is no cheap 'in-order traversal' that prints the items sorted. The only way to get sorted output is to pop everything one at a time, which is exactly what heapsort does.
Can I search a heap for an arbitrary value quickly?
No. The heap property only relates parents to children, not left to right, so a target could be anywhere in either subtree. Finding an arbitrary key is O(n), a full scan. A heap is built for one job — get the extreme — not for general lookup. If you need lookup too, pair it with a hash map (an indexed heap).
How do I change an item's priority after it's in the heap?
You can't find it in O(log n) without help, because a heap has no fast search. The fix is an indexed heap: keep a map from item to its current array index, so you can jump straight to it and then sift it up or down to its new spot. Dijkstra's decrease-key depends on this.
Min-heap or max-heap — how do I switch?
Only the comparison flips. A min-heap keeps the smallest on top; a max-heap keeps the largest. A common trick when your library only offers one is to negate the keys (push −x) to simulate the other, or supply a reversed comparator.
QuizYou pop three times from a min-heap and get 4, 7, 5 in that order. What does this tell you?
- The heap was corrupted — pops must come out sorted
- Nothing is wrong only if 5 was pushed between the second and third pop
- This is impossible; a min-heap always returns values in non-decreasing order across pops with no pushes between them
- The heap must be a max-heap
Show answer
This is impossible; a min-heap always returns values in non-decreasing order across pops with no pushes between them — With no pushes in between, successive pops from a min-heap are non-decreasing: each pop removes the current smallest, so the next smallest is at least as large. Getting 4, 7, 5 would mean 5 was hidden below 7 while 7 was the minimum, which violates the heap property. It's only possible if a smaller value (5) was pushed after the 7 was popped.
Trade-offs and when to reach for one
Reach for a heap when your access pattern is 'repeatedly take the most extreme item while items keep arriving'. That's scheduling, event simulation, graph search with priorities, and streaming top-k. The heap is a weaker fit when you need more than the extreme — full ordering, range queries, or fast lookup of arbitrary items.
- For: priority queues, Dijkstra/Prim, timers and timeouts, discrete-event simulation, keeping the top-k of a stream with a fixed-size heap, and the merge step of external sorting.
- Against (you need sorted iteration or range queries): a heap can't do either cheaply. Use a balanced search tree or a skip list, which keep full order.
- Against (you need fast lookup or membership of arbitrary keys): a heap search is O(n). Use a hash table, or pair the heap with one.
- Against (you need a hard real-time worst case with tiny constants): the O(log n) is solid, but if you truly only ever need a fixed small number of priorities, a bucket queue or a timing wheel can be O(1) per operation.
Heap vs sorted array vs balanced tree vs hash table
| Binary heap | Sorted array | Balanced tree / skip list | Hash table | |
|---|---|---|---|---|
| Get min/max | O(1) | O(1) | O(log n) | O(n) |
| Insert | O(log n) | O(n) | O(log n) | O(1) average |
| Remove min/max | O(log n) | O(n) | O(log n) | O(n) |
| Find arbitrary key | O(n) | O(log n) binary search | O(log n) | O(1) average |
| Sorted iteration / range | No (must drain) | Yes | Yes | No |
| Space overhead | None (array) | None (array) | Pointers per node | Load-factor slack |
| Best home | Priority queue / next-out | Static, read-mostly ordered | Ordered map with lookups | Unordered key lookup |
Read the table by what you need. If you only ever want the extreme while inserting and removing, the heap dominates: O(1) peek and O(log n) updates with no pointer overhead. If you also need to look items up or iterate in order, a balanced tree or skip list earns its extra cost. If you never need order at all, a hash table is faster still.
Where heaps run in the wild
- Standard-library priority queues — Python's heapq is a binary min-heap over a list; Java's PriorityQueue and C++'s std::priority_queue are binary heaps. When you reach for a priority queue in almost any language, you're using a binary heap.
- Graph algorithms — Dijkstra's shortest paths and Prim's minimum spanning tree both repeatedly pull the closest unvisited vertex, which is exactly extract-min. The priority queue is the beating heart of both.
- Timers and timeouts — the Go runtime keeps each processor's pending timers in a 4-ary min-heap keyed by fire-time, so 'which timer fires next' is the root. Language runtimes, event loops, and OS schedulers use this pattern to avoid scanning every timer each tick.
- Discrete-event simulation — the event queue is a min-heap keyed by event time; you pop the soonest event, process it, and push any new events it spawns.
- Streaming top-k — to keep the k largest items of a huge stream, hold a size-k min-heap: if a new item beats the smallest of your current top-k (the root), pop it and push the newcomer. Memory stays at k, not n.
- Heapsort — build a heap from an array, then pop repeatedly; the items come out sorted, in-place, with an O(n log n) worst case and no extra memory.
In an interview
Lead with the pitch: a binary heap is a complete binary tree kept in an array, ordered just enough that the extreme item is always at the root. Peek is O(1), push and pop are O(log n) because each walks a single root-to-leaf path, and it never needs rebalancing because it stays complete by construction. Name the uses: priority queues, Dijkstra, timers, and top-k.
Be ready to derive the index math on the spot (children at 2i+1 and 2i+2, parent at (i−1)/2), and to walk a push (append then sift up) and a pop (swap root with the last leaf, then sift down). The classic follow-ups are: why is build-heap O(n) and not O(n log n); how would you find the k largest of a huge stream in O(n log k) with O(k) memory (a size-k min-heap); and how do you support decrease-key (an indexed heap with a position map).
The trap to avoid: treating a heap as sorted. If an interviewer asks for the items in order, the answer is 'pop them all', not 'read the array'. And if they ask you to find or update an arbitrary element, flag that a bare heap can't do it in O(log n) without a side index.
Then open the simulator: push a small key and watch it sift up one path, pop the root and watch the last leaf sift down, and heapify an unordered array to see it settle bottom-up.
References & further reading
- Wikipedia — Binary heap — the array layout, sift-up/sift-down, and the O(n) build-heap analysis
- Sedgewick & Wayne — Algorithms, 4th ed.: Priority Queues (Princeton) — heap-ordered arrays, swim/sink, and heapsort with worked code and proofs
- Python — heapq (heap queue) documentation — the standard-library binary min-heap over a list; nlargest/nsmallest and merge
- Java — PriorityQueue (JDK API docs) — an unbounded priority queue backed by a binary heap
- Go runtime — runtime/time.go (timer implementation) — per-processor 4-ary min-heap of timers; siftupTimer / siftdownTimer
- CPython — Lib/heapq.py (reference implementation) — readable heappush/heappop/heapify; note its _siftup/_siftdown names are swapped vs the usual convention
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.