HeapsHeaps

Binary Min-Heap

The array-encoded complete binary tree behind min-heaps and max-heaps: parent/child indices are computed, not stored.

Commands — "insert N" or "extract", separated by commas

Empty tree

Heap array (level order)

empty

1/45Empty min-heap. Invariant: every parent ≤ its children, and the tree is complete, so it can live in an array with parent(i) = (i−1)/2.

Newly insertedElement being siftedCompared withSwappedExtracted minimum

PseudocodeLearn Binary Heap →

1insert(x): append x at the end; i = n-1
2  while i > 0 and heap[i] < heap[parent(i)]: swap; i = parent(i)   # sift up
3extract(): min = heap[0]; move last element to the root; n -= 1
4  i = 0; while smallest child < heap[i]: swap with the smaller child; continue   # sift down
5parent(i) = (i-1)//2, children = 2i+1, 2i+2

Variables

Complexity

access O(1)

search O(n)

insert O(1)

delete O(log n)

Speed