Binary heap
mediumNo pointers anywhere - node i's children are at 2i+1 and 2i+2. Push, pop, and build a heap from an arbitrary array in O(n) rather than O(n log n).
O(1) peekAverage O(log n)Worst O(log n)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How binary heap works
A binary heap stores a complete binary tree in a flat array with no pointers at all. The children of index i live at 2i+1 and 2i+2; the parent sits at (i-1)/2, rounded down. Completeness - every level full except possibly the last, filled left to right - is what makes that arithmetic airtight: no gaps, no null checks, one contiguous block of memory.
The heap property is deliberately weak: a parent beats its own two children - smaller in a min-heap, larger in a max-heap - and nothing more. Siblings are unordered; subtrees never compare. That poverty is the point. The extreme element is always at index 0, readable in O(1), and repairing the property after any change never involves more than one path between root and leaf.
Push appends at the end, keeping the tree complete, then sifts up while the newcomer beats its parent. Pop saves the root, moves the last element into the hole, and sifts it down, always swapping with whichever child beats the other. Each sift travels at most floor(log2 n) levels. Floyd's bottom-up heapify builds a heap from an arbitrary array in O(n), beating n pushes.
Step by step
- Start from the min-heap [15, 20, 30, 45, 25, 50]. Index 0 holds 15; the tree and the array are the same memory.
- Push 10: append it at index 6. Its parent is index (6-1)/2 = 2, which holds 30.
- 10 beats 30 - swap them. 10 now sits at index 2, directly below the root 15.
- 10 beats 15 too - swap again. Two swaps total and 10 is the new root: [10, 20, 15, 45, 25, 50, 30].
- Pop: return 10, move the last element 30 into the empty root slot, and start sifting down.
- 30's children are 20 and 15. 15 is the smaller one, so 30 swaps down to index 2.
- There its only child is 50, and 30 beats 50, so it stops. The root is 15 again - the smallest survivor.
Complexity
| Best case time | O(1) peek |
|---|---|
| Average time | O(log n) |
| Worst case time | O(log n) |
| Space | O(n) |
Sift up and sift down each travel one root-to-leaf path.
Reference implementation
Python
import heapq
h = []
heapq.heappush(h, 5) # O(log n)
smallest = heapq.heappop(h)
heapq.heapify(a) # O(n), not O(n log n)
# Hand-rolled min-heap, to show the mechanics:
def sift_up(h, i):
while i > 0:
parent = (i - 1) // 2
if h[parent] <= h[i]:
break
h[parent], h[i] = h[i], h[parent]
i = parent
def sift_down(h, i):
n = len(h)
while 2 * i + 1 < n:
c = 2 * i + 1
if c + 1 < n and h[c + 1] < h[c]:
c += 1
if h[i] <= h[c]:
break
h[i], h[c] = h[c], h[i]
i = cJavaScript
class MinHeap {
#h = [];
get size() { return this.#h.length; }
peek() { return this.#h[0]; }
push(v) {
this.#h.push(v);
let i = this.#h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.#h[p] <= this.#h[i]) break;
[this.#h[p], this.#h[i]] = [this.#h[i], this.#h[p]];
i = p;
}
}
pop() {
const top = this.#h[0], last = this.#h.pop();
if (this.#h.length) {
this.#h[0] = last;
let i = 0;
for (;;) {
let c = 2 * i + 1;
if (c >= this.#h.length) break;
if (c + 1 < this.#h.length && this.#h[c + 1] < this.#h[c]) c++;
if (this.#h[i] <= this.#h[c]) break;
[this.#h[i], this.#h[c]] = [this.#h[c], this.#h[i]];
i = c;
}
}
return top;
}
}Worth noticing
A heap is an array pretending to be a tree
No pointers exist. Node i's children are at 2i+1 and 2i+2, its parent at (i−1)/2. The tree drawing and the array below it are the same memory - watch both change on every swap.
The heap property is local, not global
A parent only beats its own children. There is no ordering between siblings or across subtrees - which is exactly why a heap is cheap to maintain and useless for searching. Finding an arbitrary value is still O(n).
Sift up and sift down travel one root-to-leaf path
Both walk at most the height of the tree, and a complete tree of n nodes has height ⌊log₂n⌋. That single fact gives you O(log n) push and O(log n) pop.
This is a priority queue
Dijkstra, A*, Huffman coding, event simulation, top-k streaming - all of them are 'repeatedly take the smallest/largest pending thing', and all of them use exactly this.
Common pitfalls
- Mixing index conventions. Zero-based heaps use children 2i+1 and 2i+2; the textbook formulas 2i and 2i+1 assume 1-based storage. Blending the two corrupts the heap silently.
- Sifting down toward the left child unconditionally. You must swap with whichever child beats the other, or a parent ends up losing to the child you ignored.
- Building with n pushes. That costs O(n log n); Floyd's method - sift down from the last parent, index n/2 - 1, back to 0 - does it in O(n).
- Skipping the bounds check c + 1 < n before reading the right child. The last parent frequently has only a left child.
- Expecting order beyond the root. The array is not sorted and never will be - finding an arbitrary key is still O(n).
Where it is used
- Priority queues everywhere: Dijkstra and A* pull the nearest frontier node from exactly this structure.
- Schedulers and event-driven simulation - always pop the earliest deadline or timestamp next.
- Top-k of a stream: keep a bounded heap of k elements and evict the root on overflow.
- Heap sort, and the library implementations - Python's heapq, Java's PriorityQueue - are exactly this array.
Frequently asked questions
What is the time complexity of a binary heap?
Peek is O(1) - the extreme value is always at index 0. Push and pop are O(log n) in both the average and worst case, because sift up and sift down each travel one root-to-leaf path and a complete tree of n nodes is floor(log2 n) deep. Storage is O(n), one array cell per element.
Why is building a heap O(n) instead of O(n log n)?
Floyd's method sifts down from the last parent backwards, so every subtree below is already a heap when its root is processed. Half the nodes are leaves and sift zero levels, a quarter at most one, an eighth at most two - the sum converges to O(n). Pushing n elements individually risks a full-depth sift each time.
What is the difference between a min-heap and a max-heap?
Only the comparison. A min-heap keeps every parent less than or equal to its children, so the smallest element sits at the root; a max-heap flips the inequality and serves the largest. One implementation covers both - and in libraries that only ship a min-heap, negating the keys turns it into the other.
Can you search a binary heap for a value?
Only by scanning all n cells. The heap property orders parents against their own children and nothing else - siblings and cousins are unordered - so a key gives no steering the way it does in a BST. A heap answers exactly one question fast: what is the current minimum or maximum.