Binary heap (min)

insert · extract-min O(log n)

A binary heap is a complete binary tree stored in an array (a node at index i has children at 2i+1 and 2i+2). A min-heap keeps every parent ≤ its children, so the minimum is always at the root. Insert appends then sifts up; extract-min removes the root, moves the last value up, then sifts down. Both are O(log n) — this is how priority queues are built.

Min-heap
Press ▶ to run
Edit the input and press Play

How it works

  1. Insert: append the value at the end, then swap it upward while it's smaller than its parent.
  2. Extract-min: the root is the minimum; return it.
  3. Move the last value to the root and swap it downward with its smaller child until heap order is restored.
  4. The array index drives the tree: node i has children 2i+1 and 2i+2.

Pseudocode

1insert(v):                          # O(log n)2  a.push(v); i ← a.length - 13  while i > 0 and a[i] < a[(i-1)/2]:    # smaller than parent?4    swap(a[i], a[(i-1)/2]); i ← (i-1)/2  # sift up56extractMin():                       # O(log n)7  min ← a[0]; a[0] ← a.pop()         # last value to the root8  i ← 09  loop:10    s ← the smaller child of i11    if a[i] ≤ a[s]: break12    swap(a[i], a[s]); i ← s           # sift down13  return min