cf.completefrontend
HEAPS & PRIORITY QUEUES · FOUNDATION

Binary heap (priority queue)

Keep items in an array shaped like a tree where every parent is smaller than its children, so the smallest item is always at the front.

Time O(log n) per push or popSpace O(n)19 practice problemsStep-through picture

The idea

A priority queue is a collection where you add items in any order but always take out the most urgent one first, such as the smallest number. Sorting the whole list after every new item would be slow. A binary heap does both adding and removing in O(log n).

A min-heap is a binary tree with one rule: every parent is smaller than or equal to its children. So the root is the smallest item. The tree is always filled level by level from left to right, which means it fits in a plain array with no gaps: the children of index i sit at 2 * i + 1 and 2 * i + 2, and its parent sits at Math.floor((i - 1) / 2).

JavaScript has no built-in heap or priority queue. Arrays have sort, but no structure that keeps the smallest item ready while items keep arriving. So you write a small heap yourself, which is about 30 lines, and this page shows how.

An everyday example

A sports ladder where challengers move up

Picture a club ranking shaped like a pyramid, where every player must be better than the two players just below them. A new player joins at the bottom and challenges the player above; if the newcomer is better, they swap places, and they keep challenging upward until they meet someone better. When the champion at the top retires, the last player in the pyramid steps into the top spot, then keeps swapping with the better of the two players below until the rule holds again.

How the example maps to the code
In the exampleIn the code
The pyramidthe heap array
A new player joins at the bottomheap.push(value)
Challenging the player abovecompare heap[i] with heap[parent]
The champion at the topheap[0]
The last player steps into the top spotheap[0] = last, then sift down

From the slow way to binary heap (priority queue)

  1. Start with the obvious priority queue: an unsorted array. Adding is a push, O(1), but taking out the smallest needs a scan of every item, O(n). The other obvious choice is a sorted array: taking the smallest is instant, but every insert must shift items to make room, which is also O(n). With adds and removes mixed together, one side always pays.
  2. Notice that you never need the whole order. You only need the smallest item, and after removing it, the next smallest. So keep a weaker order: a tree where each parent is at most its children. The smallest item is then at the root, and nothing else has to be fully sorted, which leaves room to repair the tree cheaply.
  3. Keep the tree complete, filled level by level from the left, so it has only about log₂ n levels and fits in an array with no gaps: the children of i are 2 * i + 1 and 2 * i + 2. A new item then goes at the end, the only spot that keeps that shape, and swaps upward past bigger parents: at most one swap per level.
  4. Removing the root leaves a hole. Fill it with the last item, again the only move that keeps the shape, then swap it down with its smaller child until both children are at least as big. Again that is one swap per level. A push that sifts up and a pop that sifts down, both on one array: that pair of loops is a binary heap.

How it works

  1. Store the heap in an array. The root (the smallest item) is heap[0]. The children of index i are at 2 * i + 1 and 2 * i + 2.
  2. To push, add the value at the end of the array.
  3. Sift it up: while it is smaller than its parent at Math.floor((i - 1) / 2), swap them and move i up to parent.
  4. To pop, remember top = heap[0], then move the last item into index 0.
  5. Sift it down: compare it with its left and right children and find the smallest of the three.
  6. If a child is smaller, swap and continue from there. Stop when the item is smaller than both children or has none. Return top.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function heapPush(heap, value) {
  2. heap.push(value);
  3. let i = heap.length - 1;
  4. while (i > 0) {
  5. const parent = Math.floor((i - 1) / 2);
  6. if (heap[parent] <= heap[i]) break;
  7. [heap[parent], heap[i]] = [heap[i], heap[parent]];
  8. i = parent;
  9. }
  10. }
  12. function heapPop(heap) {
  13. const top = heap[0];
  14. const last = heap.pop();
  15. if (heap.length > 0) {
  16. heap[0] = last;
  17. let i = 0;
  18. while (true) {
  19. const left = 2 * i + 1;
  20. const right = left + 1;
  21. let smallest = i;
  22. if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
  23. if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
  24. if (smallest === i) break;
  25. [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
  26. i = smallest;
  27. }
  28. }
  29. return top;
  30. }

How fast it is

TimeO(log n) per push or pop
Extra memoryO(n)

The tree has about log n levels and sifting moves one level per swap. The heap itself is one array of n items.

  • Best caseO(1)

    A push whose value is at least its parent, like 15 in the trace: one comparison and no swap. Reading the smallest with heap[0] is always O(1).

  • Average caseO(log n)

    A pop: the last item is usually one of the biggest, so it sinks almost to the bottom. In a test with 100,000 random values, a pop made about 14 swaps on average, while a push made only about 1.3.

  • Worst caseO(log n)

    A push of a new smallest value, which climbs to the root, or a pop whose moved item sinks to the bottom: one swap per level, about 17 for 100,000 items.

Common mistakes

  • Swapping with either child while sifting down. If you swap with the bigger child, it becomes the parent of a smaller one and the rule breaks. Always swap with the smaller child.
  • Getting the index math wrong, like children at 2 * i and 2 * i + 1. That formula is for arrays that start at index 1. With index 0 at the root, use 2 * i + 1 and 2 * i + 2.
  • Popping from an empty heap and then using undefined as a value. Check heap.length (or size) first.
  • Sorting the array after every push to fake a heap. It works but costs O(n log n) per push instead of O(log n).

When to use it

Look for these clues in a problem:

  • You repeatedly need the smallest or largest item while items keep being added.
  • The question says "next most urgent", "earliest deadline", "cheapest so far", or "highest priority".
  • Sorting once isn't enough, because new items arrive between the removals.
  • You need the k smallest or k largest items, or to merge several sorted lists.

Check yourself

Answer each one in your head first, then open it.

In the array [2, 7, 3, 12, 9, 15], which items are the children of 7?

7 is at index 1, so its children are at 2 * 1 + 1 = 3 and 4: 12 and 9.

Why must sift-down swap with the smaller child?

The child that moves up becomes the parent of the other child. Only the smaller one is at most the other, so only that swap keeps the order.

Is a heap's array sorted?

No. Only the root is sure to be the smallest. In the trace, the heap [2, 7, 3, 12, 9, 15] has 7 before 3.

Why does a pop move the last item to the root instead of moving a child up?

Taking the last item keeps the array without gaps, so the tree stays complete and short. Moving children up would leave a hole somewhere in the middle.

How many levels does a heap of 1,000 items have?

10. Each level holds twice as many items as the one above, so 10 levels hold up to 1,023 items, and 9 levels only 511.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 19 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Every operation keeps two properties. The shape: the array has no gaps, so the tree is filled level by level and has about log₂ n levels. The order: every parent is at most its children, so following parents upward never gets bigger, and the root heap[0] is the smallest item.

heapPush adds at the end, which keeps the shape. The order can now be broken only between the new item and its parent. Each swap moves the new item up past a bigger parent, and the parent moves down onto a spot whose children were already its own descendants, so it is still at most them. The only possible problem moves up one level per swap, and when the loop stops at a smaller-or-equal parent or at the root, the order holds everywhere.

heapPop takes the root, which is the smallest item, then moves the last item into the root, which keeps the shape. Now the order can be broken only between the root and its children. Swapping with the smaller child puts the smallest of the three on top, which is at most the other child, so that spot is fixed and the only possible problem moves down one level. When the item is at most both children, or has none, the order holds again.

Going deeper

4 more ideas

Why the smallest item is always at index 0

The rule says every parent is less than or equal to its children. Follow any item up through its parents: each step gets smaller or stays equal. Every path ends at the root, so nothing can be smaller than the root. Push and pop each break the rule at one spot only, and sifting moves that one item until the rule holds everywhere again.

Why each operation is O(log n)

The tree is filled level by level, so a heap with n items has about log n levels. Sifting up or down moves one level per swap, so it does at most log n swaps. Reading the smallest item without removing it is just heap[0], which is O(1).

A reusable heap class with a compare function

Real problems store objects, not just numbers, and sometimes want the largest item first. A common pattern is a MinHeap class that takes a compare(a, b) function, like Array.prototype.sort does: a negative result means a comes out first. It has push(item), pop(), peek() (look at heap[0]), and a size getter. Use (a, b) => a - b for smallest first, (a, b) => b - a for largest first, or compare fields such as a.time - b.time. The other heap pages use this class.

Building a heap from an array at once

Pushing n items one by one costs O(n log n). Instead, you can put all items in the array and sift down every parent, from index Math.floor(n / 2) - 1 back to 0. Most items are near the bottom and move only a little, so this "heapify" step costs only O(n) in total.

Work it by hand

Every step in a table, with why

Push six numbers into an empty min-heap, then pop once. Each row is one pass of a loop or one call.

heapPush 12, 7, 15, 3, 9, 2 in that order, then heapPop(heap)

StepCalliCompared withheap afterWhat happensWhy
1push 120-[12]i is 0: no parentThe first item goes to index 0. The loop while (i > 0) doesn't run.
2push 71heap[0] = 12[7, 12]12 > 7: swap, i = 07 starts at index 1. Its parent, at Math.floor((1 - 1) / 2) = 0, is bigger, so they swap and 7 becomes the root.
3push 152heap[0] = 7[7, 12, 15]7 <= 15: stop15 is bigger than its parent, so the rule already holds. No swap.
4push 33heap[1] = 12[7, 3, 15, 12]12 > 3: swap, i = 13 starts at index 3, whose parent is index 1.
5push 31heap[0] = 7[3, 7, 15, 12]7 > 3: swap, i = 03 keeps climbing and becomes the root: two swaps, one per level.
6push 94heap[1] = 7[3, 7, 15, 12, 9]7 <= 9: stopIndex 4's parent is index 1, which holds 7. No swap.
7push 25heap[2] = 15[3, 7, 2, 12, 9, 15]15 > 2: swap, i = 2Index 5's parent is index 2. 2 only meets the parents on its own path, never 7 or 12.
8push 22heap[0] = 3[2, 7, 3, 12, 9, 15]3 > 2: swap, i = 02 reaches the root.
9pop0-[15, 7, 3, 12, 9]top = 2, last = 15 to rootThe root is the answer. The last item fills the hole, so the tree keeps its shape.
10pop0children 7, 3[3, 7, 15, 12, 9]smallest = 2: swap, i = 2left = 1 and right = 2. The smaller child is 3, so 15 swaps with it. Swapping with 7 would put 7 above 3 and break the rule.
11pop2no children[3, 7, 15, 12, 9]smallest === i: stopIndex 2's children would be at 5 and 6, past the end. 15 is now a leaf, and the pop returns 2.

The pop returns 2, and the new smallest item, 3, is at the root. The six pushes made 5 swaps in total and the pop made 1, never more than 2 per call, because a heap of 6 items has only 3 levels.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Binary heap (priority queue)O(log n)O(n)Items keep arriving and leaving, and you always need the smallest or largest next. Each push or pop is O(log n).
Sorted arrayO(n)O(n)You add rarely and read in order often, or need the full sorted order at any time. Each insert shifts items.
Unsorted array with a scanO(n)O(n)The queue only ever holds a handful of items, so a scan for the smallest costs less than any bookkeeping.
Balanced search treeO(log n)O(n)You also need to delete any item, read both the smallest and the largest, or walk the items in order. JavaScript has none built in.

Extra memory: O(n) for the array itself, and O(1) extra per operation: just i, parent, left, right, and smallest.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Binary heap (priority queue) and the other approaches, on a scale where each line up is 10 times more steps.
  • Binary heap (priority queue), Balanced search tree O(log n)
  • Sorted array, Unsorted array with a scan O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Binary heap (priority queue)31020
Sorted array101,0001 million
Unsorted array with a scan101,0001 million
Balanced search tree31020

Inputs that need care

5 tricky inputs
Popping an empty heap: heapPop([])
top is undefined, heap.pop() returns undefined, the heap.length > 0 check skips the sift, and it returns undefined. Check heap.length before popping, because undefined compares badly with numbers.
Popping the only item: heapPop([4])
heap.pop() empties the array, so heap.length > 0 is false and nothing is put back. Without that check, heap[0] = last would put 4 right back in.
Equal values: pushing 5 into [5, 8]
heap[parent] <= heap[i] is 5 <= 5, true, so it stops without a swap. Equal items don't come out in the order they went in; add a counter as a second key if that matters.
Objects instead of numbers
<= on two objects compares their string forms, like "[object Object]", so the order is meaningless. Compare a field, such as heap[parent].time <= heap[i].time, or use a MinHeap class with a compare function.
Changing an item's priority after it was pushed
The heap doesn't notice, and the order breaks. Either sift that item up or down from its index (you need a Map from item to index to find it), or push a new copy and skip stale copies when they reach the top.

Variations and follow-ups

Twists interviewers add

Max-heap

Flip both comparisons: heap[parent] >= heap[i] in the push, and pick the larger child in the pop. With a compare-function class, just pass (a, b) => b - a. Storing negated numbers in a min-heap also works, but only for numbers.

Heap sort

Build a max-heap inside the array, then repeatedly swap the root with the last unsorted item and sift the new root down within the shrinking heap. That sorts in place in O(n log n) with O(1) extra space, but equal items may change order.

Lazy deletion

To remove or update any item, mark the old version as stale, for example in a Set, and push the new version. When a stale item reaches the top, pop it and ignore it. This is simpler than tracking indexes, and it is how many shortest-path codes handle distance updates.

d-ary heap

Give each node d children instead of 2: the children of i are at d * i + 1 up to d * i + d. The tree gets shorter, so pushes get faster, but each sift-down step compares d children. With d = 4 it is often faster in practice, because the children sit next to each other in memory.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "repeatedly take the smallest", "next most urgent", "k-th largest", "merge sorted", or anything that needs the best item while items keep arriving.
  • In JavaScript you usually have to write the heap. Say so, and write a small class with push, pop, peek, size, and a compare function. It takes a few minutes and serves the rest of the problem.
  • Explain the two properties out loud: the shape (no gaps, so about log n levels and simple index math) and the order (every parent at most its children). Then each method is just "repair the order along one path".
  • Test by hand: a push into an empty heap, a pop of the only item, pushes of equal values, and popping until empty while checking that the values come out sorted.
  • A common follow-up: "how do you build a heap from n items quickly?". Answer: put them in the array and sift down every parent from index Math.floor(n / 2) - 1 back to 0. That costs O(n), because most items sit near the bottom and move only a little.

Where frontend code uses it

The same idea in real UI code
  • React's scheduler package, which decides which update to run next, keeps its tasks in a small min-heap ordered by expiration time.
  • Node.js runs on libuv, which keeps its pending timers in a min-heap so the next timer to fire is always at the top.
  • A notification center that shows the most urgent message first, while new messages keep arriving, is a priority queue.
  • Route planners in map apps and pathfinding in browser games use a heap to pick the next closest point in Dijkstra's or A* search.

Related algorithms