Home/Trees/Binary heap
Search algorithmsCTRL K

Binary heap

· push, pop · a complete tree inside an array
/trees/binary-heap
SIZE
1/ 12
keys in the heap
SWAPS
0
parent with child
COMPARISONS
0
key against key
HEIGHT
1
levels, root included
POPPED
—
in order, largest first
just pushedsiftingcompared withlast leaf, moving to the root
12 keys · seed 7 · 77 steps
step 0 / 76
Keys12
binary_heap.ts
1
function push(heap: number[], key: number) {
2
  heap.push(key);
3
  let index = heap.length - 1;
4
  while (index > 0 && heap[index] > heap[parent(index)]) {
5
    swap(heap, index, parent(index));
6
    index = parent(index);
7
  }
8
}
9
function pop(heap: number[]): number {
10
  const top = heap[0];
11
  heap[0] = heap[heap.length - 1];
12
  heap.pop();
13
  siftDown(heap, 0);
14
  return top;
15
}
16
function siftDown(heap: number[], index: number) {
17
  while (true) {
18
    const left = 2 * index + 1, right = left + 1;
19
    let largest = index;
20
    if (left < heap.length && heap[left] > heap[largest]) largest = left;
21
    if (right < heap.length && heap[right] > heap[largest]) largest = right;
22
    if (largest === index) return;
23
    swap(heap, index, largest);
24
    index = largest;
25
  }
26
}
CURRENT STEP
line 2

Push 24: append it at index 0, the next free slot of the complete tree.

// how it works

Understanding Binary heap

binary heap · the parent always beats its children
01

The idea

A binary heap is a complete binary tree, every level full except the last, which fills left to right, stored in an array with no pointers at all: the children of index i sit at 2i + 1 and 2i + 2, and its parent at ⌊(i − 1) / 2⌋. The one rule is that every parent is at least as large as its children, so the maximum is always at index 0.

Push appends the key at the end and sifts it up, swapping with its parent while it is larger. Pop takes the root, moves the last leaf into its place and sifts it down, swapping with the larger child while one of them is larger. Both walk one root-to-leaf path, so both cost the height, log₂ n.

02

The four stages

1
appendthe key takes the next free slot
2
sift upswap with the parent while larger
3
poproot out, last leaf into its place
4
sift downswap with the larger child while smaller
03

Complexity

best
O(1)push of a small key, peek of the maximum
average
O(log n)push climbs about 1.6 levels on random keys
worst
O(log n)push and pop walk the full height
space
O(n)the array, nothing else
04

Versus its siblings

COMPARISONS · 1 000 000 PUSHES THEN 1 000 000 POPS
binary heap
42M
balanced bst
60M
sorted array
500B
unsorted array
500B
fibonacci heap
22M
the array versions pay O(n) on one of the two operations
05

Pseudocode

PUSH(heap, key)
  append key; index ← last
  while index > 0 and heap[index] > heap[parent]: swap them; index ← parent
POP(heap)
  top ← heap[0]; move the last key to index 0; shrink
  index ← 0; while a child is larger: swap with the larger child; descend
  return top
06

When to use

Priority queues everywhere: Dijkstra and A*, event simulation, schedulers, top-k of a stream, Huffman coding.
Heap sort, and heapify in O(n) when the whole array arrives at once.
07

Pitfalls

A heap is not sorted: only the root is known; in-order traversal means nothing here.
Changing a key in place breaks the property; use decrease-key with a position map, or push a duplicate and skip stale entries.
Building by n pushes costs O(n log n); Floyd's bottom-up heapify does it in O(n).
08

History

J. W. J. Williams introduced the binary heap in 1964 as the engine of heapsort, and Robert Floyd improved the construction to linear time the same year. The array layout without pointers is what made it practical; Fibonacci and pairing heaps later improved the asymptotics of decrease-key but rarely beat it in practice.

Back to Trees