Heaps / Priority Queue

A heap gives you the smallest (or largest) item in O(1) and adds or removes items in O(log n). It is the tool for top-K, merging sorted streams, running medians and scheduling.

Overview

What a heap is

A heap is a binary tree stored in a plain array. It keeps one rule, the heap property: in a min-heap every parent is less than or equal to its children, so the smallest item is always at the root. A max-heap flips the rule, so the largest item is at the root.

The tree is always complete: every level is full except the last, which fills from the left. That shape is why the height stays about log2(n) and why no pointers are needed.

The same heap is the array [1, 3, 5, 7, 8, 9, 10, 12, 15]. Parent and child positions come from arithmetic on the index.

Parent — (i - 1) // 2 — index 0, value 1
Left child — 2i + 1 — index 3, value 7
Right child — 2i + 2 — index 4, value 8

A heap is only partly ordered. It knows the minimum, but the array is not sorted, and finding any other value means scanning all of it.

Push: add at the end, then sift up

To add a value, put it in the next free slot at the end of the array. Then compare it with its parent and swap while it is smaller. This is called sift up (or bubble up). It climbs at most the height of the tree, so push is O(log n).

Trace: push 2 into [1, 3, 5, 7, 8, 9, 10, 12, 15].

1 — 9 (appended) — 4, value 8 — 2 1 — stop

Result: [1, 2, 5, 7, 3, 9, 10, 12, 15, 8]. Python's heapq.heappush gives the same array.

Pop: move the last item to the root, then sift down

To remove the minimum, take the root, move the last item into its place, and shrink the array by one. Then push that item down: swap it with its smaller child while that child is smaller than it. Pop is also O(log n).

Trace: pop from [1, 3, 5, 7, 8, 9, 10, 12, 15]. The root 1 is returned and 15 moves to index 0.

1 — 0 — 3, 5 — 3 at index 1 — swap
2 — 1 — 7, 8 — 7 at index 3 — swap
3 — 3 — 12 — 12 at index 7 — swap
4 — 7 — none — none — stop

Result: [3, 7, 5, 12, 8, 9, 10, 15], which matches heapq.heappop.

Building a heap in O(n)

Pushing n items one by one costs O(n log n). Building bottom-up is faster: run sift down on every non-leaf node, starting from the last one (index n // 2 - 1) and moving toward the root. Half the nodes are leaves and need no work, and most of the rest sit near the bottom where sift down is short.

0 (leaves) — 8 — 0 — 0
1 — 4 — 1 — 4
2 — 2 — 2 — 4
3 (root) — 1 — 3 — 3
All — 15 — 11, fewer than n

In general the sum of heights over all nodes is less than n, so building is O(n). Python's heapq.heapify does this in linear time.

Top K: keep a min-heap of size K

To find the K largest values, keep a min-heap of the best K seen so far. Its root is the smallest of them, the one to evict when a bigger value arrives. When the input ends, the root is the K-th largest. Each of the n items costs at most O(log K), so the total is O(n log K) with O(K) memory.

Trace: K-th largest of [3, 2, 1, 5, 6, 4] with K = 2.

3, 2 — empty — fill the first K, then heapify — [2, 3]
1 — [2, 3] — 1 is not > 2 — [2, 3]
5 — [2, 3] — 5 > 2, replace root — [3, 5]
6 — [3, 5] — 6 > 3, replace root — [5, 6]
4 — [5, 6] — 4 is not > 5 — [5, 6]

The root, 5, is the 2nd largest. For the K smallest, flip it: keep a max-heap of size K.

Two heaps: a running median

To report the median of a growing stream, split the values in half. A max-heap holds the smaller half, so its root is the largest small value. A min-heap holds the larger half, so its root is the smallest large value. Keep the sizes equal, or let the small side have one extra. The median is then one root or the average of both roots.

Each new value goes into small, then the largest of small moves to large; if large becomes bigger, its smallest moves back. Trace for the stream 5, 15, 1, 3:

5 — [5] — [] — 5
15 — [5] — [15] — (5 + 15) / 2 = 10
1 — [5, 1] — [15] — 5
3 — [3, 1] — [5, 15] — (3 + 5) / 2 = 4

Each add is O(log n) and each median query is O(1).

Merge K sorted lists

Put the head of each list in a min-heap. Pop the smallest, append it to the output, and push the next item from the same list. The heap never holds more than K items, so N items in total cost O(N log K).

Heaps in Python, Java and JavaScript

Min-heap — heapq functions on a list — new PriorityQueue<>() — no built-in heap; write a small class
Max-heap — push negated numbers; Python 3.14 adds heappush_max and friends — new PriorityQueue<>(Collections.reverseOrder()) — pass a reversed comparator to your class
Build from data — heapify(list), linear time — new PriorityQueue<>(collection) — your own bottom-up build
Peek, push, pop — h[0], heappush, heappop — peek, offer, poll — your own methods
Push and pop in one step — heapreplace, heappushpop — none; poll then offer — your own replaceTop

Two library details matter in practice. Java's PriorityQueue gives O(log n) offer and poll but O(n) remove(Object) and contains, and its iterator does not visit items in priority order. Python compares tuples item by item, so push (priority, count, item): the counter breaks ties and keeps Python from ever comparing two items that cannot be compared.

What you will be able to do

Draw a heap as a tree and as an array, and compute parent and child indexes.
Trace push (sift up) and pop (sift down) by hand, and explain why heapify is O(n).
Pick the right heap for top-K, K closest, merge K sorted, running median and scheduling problems.
Write each of those patterns in Python, Java or JavaScript and state the time and space cost.

When to use it

You need the smallest or largest item again and again while items keep arriving
Top K largest, smallest, most frequent or closest items
Merging K sorted lists, arrays or streams
A running median or other split-in-half statistic
Scheduling: always run the next task by time or priority
Greedy graph algorithms such as Dijkstra and Prim

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio