HeapsData structureaka heap, array heap, implicit heap

Binary Heap

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

▶ Visualize Pattern: Heap / Priority Queue Practice (7)

Progress

Definition

A binary heap is a complete binary tree that satisfies the heap property — every parent is ordered relative to its children (≤ for a Min-Heap, ≥ for a Max-Heap) — stored in a flat array so that no child pointers are needed. It is the standard implementation of a Priority Queue.

The two facts that make it work are independent: completeness lets the tree live in an array with parent (i-1)/2 and children 2i+1, 2i+2; the heap property puts the extreme element at index 0. Together they give O(1) peek, O(log n) push/pop, and O(n) bulk build.

This page covers the generic mechanics — array layout, sift-up, sift-down, bottom-up heapify, and the comparator abstraction. The min and max variants only differ in the comparison.

complete binary treeimplicit treepriority queueheapifysift

Intuition

A mental model before the formal terms.

Number the nodes of a full binary tree level by level starting at 0. Node i always has children 2i+1 and 2i+2 — a rule you can check on paper for the first few rows. Because the tree fills left to right with no gaps, the array has no holes, and the tree shape is fully determined by n.

Restoring order after a change is like a bubble in water: a too-light element floats up (sift-up), a too-heavy one sinks (sift-down). Each move covers one level, and there are only log₂ n levels.

How it works

Layout: a[0] is the root. For index i: parent = (i - 1) >> 1, left = 2i + 1, right = 2i + 2. The last internal node is at n/2 - 1; everything after is a leaf.
Sift-up(i): while i > 0 and a[i] should be above a[parent], swap and move to the parent.
Sift-down(i): pick the child that should be highest; if it beats a[i], swap and continue from that child; otherwise stop.
Push(x): a.append(x); sift-up from the last index.
Pop(): save a[0]; move a[n-1] to index 0; shrink; sift-down from 0.
Heapify(array): for i from n/2 - 1 down to 0, sift-down(i). Leaves are trivially heaps, so processing internal nodes bottom-up merges valid sub-heaps.
Comparator: implement once with a less(x, y) function; a min-heap passes x < y, a max-heap passes x > y, and arbitrary priorities (tuples, objects) work unchanged.

Why it works

Index arithmetic is correct because level d of a complete binary tree occupies indices 2^d - 1 … 2^(d+1) - 2; doubling an index plus one lands exactly on the first child in the next level.

Sift-up and sift-down each maintain the invariant that all subtrees *not* on the current path are valid heaps, and the path itself has at most one violation, which moves one level per step.

Heapify is O(n), not O(n log n): a node at height h sifts at most h levels, and there are about n / 2^(h+1) nodes at height h. Summing h · n / 2^(h+1) over all h gives n · Σ h/2^(h+1) < n · 2 = O(n).

Operations

Operation	Description	Cost
peek	Return `a[0]`, the extreme element under the comparator.	O(1)
push	Append and sift up.	O(log n)
pop	Swap root with last, shrink, sift down.	O(log n)
heapify	Bottom-up build from an arbitrary array.	O(n)
replace-top	Overwrite the root and sift down (cheaper than pop + push).	O(log n)
update-key(i)	Change a key at a known index, then sift up or down depending on direction.	O(log n)
delete(i)	Move the last element into i; sift up or down.	O(log n)
search	No secondary index; linear scan.	O(n)

Recognition

How to tell a problem wants this.

Any problem that says "priority", "k-th largest/smallest", "closest", "earliest", "merge sorted streams", or "schedule by deadline".
Repeated min/max extraction from a set that keeps growing — an O(n) scan per extraction would be O(n²) total.
You need O(1) extra space and guaranteed O(n log n) sorting → Heap Sort on this structure.

“k most frequent” → Heap / Priority Queue “weighted graph” → Shortest Path (Weighted)“maximum number of non-overlapping” → Greedy

Interactive demo

Play, step, change the input. ← → and space work too.

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

Pseudocode

1parent(i) = (i-1)/2; left(i) = 2i+1; right(i) = 2i+2
2sift_up(i): while i > 0 and less(a[i], a[parent(i)]): swap; i = parent(i)
3sift_down(i):
4  loop: m = i; for c in (left(i), right(i)): if c < n and less(a[c], a[m]): m = c
5        if m == i: break; swap(i, m); i = m
6push(x): a.append(x); sift_up(n-1)
7pop(): top = a[0]; a[0] = a[n-1]; n -= 1; sift_down(0); return top
8heapify(): for i = n/2-1 down to 0: sift_down(i)

Implementation

1from typing import Callable, Generic, TypeVar
2 
3T = TypeVar("T")
4 
5 
6class BinaryHeap(Generic[T]):
7    """Comparator-driven heap. less(x, y) is True when x must sit above y."""
8 
91 · Storage, comparator, heapify constructor
10    def __init__(self, less: Callable[[T, T], bool] = lambda x, y: x < y, items=None):
11        self.less = less
12        self.a: list[T] = list(items) if items is not None else []
13        for i in range(len(self.a) // 2 - 1, -1, -1):
14            self._sift_down(i)
15 
162 · Sift up
17    def _sift_up(self, i: int) -> None:
18        a = self.a
19        while i > 0:
20            p = (i - 1) // 2
21            if not self.less(a[i], a[p]):
22                break
23            a[i], a[p] = a[p], a[i]
24            i = p
25 
263 · Sift down
27    def _sift_down(self, i: int) -> None:
28        a, n = self.a, len(self.a)
29        while True:
30            l, r, m = 2 * i + 1, 2 * i + 2, i
31            if l < n and self.less(a[l], a[m]):
32                m = l
33            if r < n and self.less(a[r], a[m]):
34                m = r
35            if m == i:
36                return
37            a[i], a[m] = a[m], a[i]
38            i = m
39 
404 · Push and pop
41    def push(self, x: T) -> None:
42        self.a.append(x)
43        self._sift_up(len(self.a) - 1)
44 
45    def pop(self) -> T:
46        top = self.a[0]
47        last = self.a.pop()
48        if self.a:
49            self.a[0] = last
50            self._sift_down(0)
51        return top
52 
535 · Peek, replace-top, size
54    def peek(self) -> T:
55        return self.a[0]
56 
57    def replace_top(self, x: T) -> T:
58        """One sift instead of two (heapq.heapreplace equivalent)."""
59        top = self.a[0]
60        self.a[0] = x
61        self._sift_down(0)
62        return top
63 
64    def __len__(self) -> int:
65        return len(self.a)
66 
67 
68# max_heap = BinaryHeap(lambda x, y: x > y)  # in production: heapq

Walkthrough

A generic comparator-driven heap: less(x, y) True puts x above y, so lambda x, y: x > y yields a max-heap.
Generic[T] plus a Callable type hint documents the contract precisely.
Both sifts use tuple-swap assignment; _sift_down picks m as the highest-priority of the three candidates.
replace_top mirrors heapq.heapreplace: one O(log n) sift instead of pop + push.
In real code prefer heapq (C-implemented, min-only); this class exists to make the mechanics and the comparator explicit.

Complexity (this implementation)

time O(log n) push/pop, O(n) heapify · space O(n)

Pure-Python sifts are ~10-30x slower than heapq's C implementation.

Language notes

heapq cannot take a comparator at all — you encode priority in the elements (tuples, negation, or __lt__); this class shows the comparator alternative.
range(len(a) // 2 - 1, -1, -1) is the canonical bottom-up heapify order.
list.pop() (no index) is O(1); list.pop(0) would be O(n).

Common mistakes in this language

Writing less(a[p], a[i]) in sift-up — inverted comparison turns the heap inside out.
Using this in performance-sensitive code where heapq suffices.
Forgetting if self.a: after popping the last element and indexing an empty list.

Language differences that matter here

Comparator style: C++ takes a comparator TYPE (std::greater<T>), JS/TS/Python take a comparator VALUE (closure) — same idea, different binding time.
Python heapq refuses custom comparators entirely; priorities must live in the elements. The other languages parameterize the heap itself.
Integer division for the parent index: (i-1)>>1 in JS/TS, (i-1)//2 in Python, (i-1)/2 on integers in C++ — JS needs the shift (or Math.floor) because / is float division.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Root only.
Search	O(n)	O(n)
Insert	O(1)	O(log n)
Delete	O(log n)	O(log n)	Root, or any index if known.
Update	O(log n)	O(log n)	Requires the index.
Peek	O(1)	O(1)
Push	O(1)	O(log n)
Pop	O(log n)	O(log n)
Heapify	O(n)	O(n)
Merge	O(n)	O(n)	Concatenate and re-heapify.
Space	O(n)		No per-node overhead: the array is the whole structure.

Advantages & disadvantages

Advantages

Pointer-free: the array is compact and cache-friendly; memory overhead is zero beyond the elements.
Simple, ~40-line implementation with no rebalancing logic, unlike a Binary Search Tree or AVL Tree.
O(n) heapify makes building from a batch cheaper than any comparison sort.
Generalises to a d-ary heap (children d·i + 1 … d·i + d) to trade shallower trees for more comparisons per level.

Disadvantages

No fast search, no ordered iteration, no successor/predecessor queries.
Decrease-key requires an external index map — Fibonacci Heap and pairing heaps do it natively.
Merging two heaps is O(n) (concatenate + heapify); mergeable heaps (leftist, binomial) do it in O(log n).
Worst-case O(log n) for push even when the average is O(1).

Use cases

Backing store for a Priority Queue in every mainstream standard library.
Heap Sort: in-place, O(n log n), O(1) space.
Dijkstra's Algorithm, Prim's Algorithm, A* Search: extract the minimum tentative cost.
Streaming order statistics: k-th largest, top-k frequent, running median.
Timer wheels and event loops: next event to fire.

Use it when

Implementing a priority queue with predictable O(log n) operations and minimal memory.
Bulk-building from n items (heapify is O(n)).
In-place sorting with O(1) extra space.
Any greedy algorithm that repeatedly needs the current extreme.

Avoid it when

You need frequent decrease-key on huge graphs with far more edges than vertices — a Fibonacci Heap or pairing heap wins asymptotically (rarely in practice).
Frequent merges of two queues — use a leftist, binomial, or Fibonacci heap.
Ordered traversal, range queries, or predecessor/successor — use a balanced BST or Skip List.
The set is static and you need many "is x present" checks — a Hash Set.

Alternatives

Fibonacci Heap Binary Search Tree Skip List Monotonic Queue

Compare: Heap vs Priority Queue

Common mistakes

Using (i - 1) / 2 on index 0 without the i > 0 guard (in languages with integer division it gives 0 and loops forever with a bad comparator).
Building with n pushes (O(n log n)) when heapify (O(n)) is available.
Sift-down that checks only the left child, or that stops after one swap.
Mutating an element's key in place without re-sifting — silently corrupts the heap.
Ignoring the "last element was the root" case after pop, causing an out-of-range sift.

Interview patterns

Implement a priority queue from scratch (push, pop, peek, heapify) — a common warm-up.
Explain why heapify is O(n) — a frequent follow-up.
Kth largest / top-k with a bounded heap.
Two-heap median; merge k sorted lists; meeting rooms II.
Convert a min-heap into a max-heap with a comparator or key negation.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Where does O(n log n) come from?Beginner
Top K from a streamIntermediate
When a hash map is the wrong choiceIntermediate

Mock interviews

Kth Largest Element in an ArrayIntermediate
Network Delay TimeAdvanced
Merge IntervalsIntermediate

Interview problems

Merge k Sorted Listshard Kth Largest Element in an Arraymedium Top K Frequent Elementsmedium Kth Largest Element in a Streameasy Find Median from Data Streamhard Task Schedulermedium Meeting Rooms IImedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related