Heaps & Priority Queues

A heap answers exactly one question fast: "what is the smallest (or largest) thing I am holding right now?" It does not answer "is x in here" and it does not answer "give me everything in order" without doing real work first. That narrowness is the whole design - a heap gives up almost every property a sorted structure has, in exchange for O(log n) insert and O(log n) extract-the-extreme, forever.

It is also the quiet workhorse behind "top k", "merge k sorted lists", Dijkstra, and any problem whose next step depends on "the best option so far."

1. The heap property

A min-heap is a binary tree where every parent is <= both of its children. A max-heap flips the inequality: every parent is >= both children. That is the entire rule, and it says nothing else - nothing about left versus right, nothing about one sibling versus another, nothing about any node compared to a node it is not a direct ancestor or descendant of.

That single restriction has two consequences worth stating plainly, because both are exactly what people expect a heap to not do:

⚠

A heap is not sorted, and you cannot search it

The heap property constrains parent-child pairs only, so level order is not sorted order and a target value is not "left or right" of anything. Above, 3 sits before 2 even though 3 > 2 - they are siblings, not a parent-child pair, so nothing enforces an order between them. That is also why looking for an arbitrary value in a heap is O(n): there is no comparison you can make at the root that rules out an entire subtree, the way a BST's ordering does. A heap only ever answers questions about its root.

2. A complete tree lives in an array

A heap is always a complete binary tree: every level is full except possibly the last, and the last level fills strictly left to right, with no gaps. Completeness is the whole reason a heap can be packed into a plain array with no pointers at all - the level-order array of a complete tree never has a hole, so index arithmetic alone finds every parent and child.

You have	Formula (0-indexed)	On the array above
index i	itself	index 1 holds 3
i's left child	2*i + 1	index 3 holds 7
i's right child	2*i + 2	index 4 holds 8
i's parent (i > 0)	(i - 1) // 2	index 0 holds 1
the last non-leaf index	(n // 2) - 1	used by heapify - see section 5

def parent(i): return (i - 1) // 2

def left(i): return 2 * i + 1

def right(i): return 2 * i + 2

This is the exact same array you saw on Representation for a level-order-serialized binary tree. A heap does not need a new storage idea - it is the special case where the level-order array happens to have no null holes, because the tree is always complete.

3. Sift up: push

Pushing a value is two moves: append it as the new last leaf, then let it swim up past any parent it is smaller than (min-heap). Each step is one comparison and, at most, one swap - and the path it can possibly take is bounded by the tree's height, which is log n for n elements. That bound is where push gets its O(log n).

Pushing 0 onto the heap. It starts as the new last leaf and swaps upward with its parent at every step, because 0 is smaller than everything above it - the worst case, all the way to the root.

def push(heap, value):

heap.append(value)

i = len(heap) - 1

while i > 0:

p = (i - 1) // 2

if heap[p] <= heap[i]:

break # parent is already smaller - done

heap[p], heap[i] = heap[i], heap[p]

i = p

FIG. HEAP SIFT UP● INTERACTIVE

visualization loads as you reach it

Mnemonic

Sift UP starts at the bottom and climbs; sift DOWN starts at the top and sinks. push only ever disturbs the single root-to-leaf path the new element sits on, which is why it never needs to look at any other branch of the tree.

4. Sift down: pop

Popping the minimum has to solve a harder problem: the root is leaving, and something has to become the new root without breaking completeness. The answer is to swap the last leaf into the root's place, shrink the array by one, then let that element sink down past whichever child is smaller, until it finds a spot where it is <= both children or it runs out of children.

Popping the heap left by the push above. The last leaf takes the root's place, then sinks down by always swapping with its SMALLER child, until it lands back where the run started - the same heap we began with.

def pop(heap):

heap[0], heap[-1] = heap[-1], heap[0]

root = heap.pop() # the actual minimum, already swapped out

n = len(heap)

i = 0

while True:

smallest, l, r = i, 2 * i + 1, 2 * i + 2

if l < n and heap[l] < heap[smallest]:

smallest = l

if r < n and heap[r] < heap[smallest]:

smallest = r

if smallest == i:

break # both children are already >= i

heap[i], heap[smallest] = heap[smallest], heap[i]

i = smallest

return root

FIG. HEAP SIFT DOWN● INTERACTIVE

visualization loads as you reach it

The last element is the only one that can be removed without breaking completeness, which is why it is the one that moves in - not the root's child.

Deleting the root and promoting a child would leave a hole somewhere in the middle of a still-full last level; nothing else in the tree can fill that hole without the same problem recurring. Taking the last leaf out costs nothing structurally - it was always the "newest" slot - and handing its value to the root turns "delete the root" into "reinsert one value," which sift-down already knows how to fix.

⚠

Sift down swaps with the smaller child, never blindly the left one

Comparing only against heap[left] and forgetting heap[right] produces a structure that fails the heap property the first time the right subtree holds the smaller value. Both children have to be checked and the swap has to go to whichever is smaller (min-heap) - smallest = i, then two independent if checks against l and r, exactly as above. Swapping with "the first child that is smaller than me" instead of "the smallest of the two children" is the same bug wearing a different hat.

5. Building a heap in linear time

Given n unsorted values, pushing them one at a time costs n pushes at O(log n) each - O(n log n) total. Heapify does better: O(n). The trick is to sift down starting from the last non-leaf node and work backward to the root, rather than sifting up from an empty heap.

def heapify(heap):

n = len(heap)

for i in range(n // 2 - 1, -1, -1): # last non-leaf down to the root

_sift_down(heap, i, n)

The O(n) bound looks surprising until you count how far each node can possibly sink. A node at height h (measuring up from the leaves) can sift down at most h levels, and there are roughly n / 2^(h+1) nodes at each height. Summing cost over every height:

total work <= sum over h of (n / 2^(h+1)) * h

= n * sum over h of h / 2^(h+1)

= n * 1 (that infinite sum converges to 1)

= O(n)

Half the nodes are leaves and do zero work; a quarter are one level up and do at most one swap; an eighth do at most two - the work per node shrinks geometrically exactly as fast as the node count does, and the product sums to a constant, not a log n.

heapq.heapify uses exactly this bottom-up pass, so building a heap from a list you already have is always the right move over n individual heappush calls. heapq.heapify(data) mutates data in place in O(n); looping heappush(heap, x) for x in data builds the same heap in O(n log n).

6. heapq in practice

Python's heapq module implements a min-heap only - there is no max-heap variant, and no way to ask it to compare "the other way."

warning

heapq is always a min-heap. To use it as a max-heap, negate every value going in and negate it again coming out: heappush(h, -x), then -heappop(h). This is the standard trick, not a workaround - every "max-heap" you see in Python solutions is a min-heap of negated values.

import heapq

 

h = [5, 1, 8, 3]

heapq.heapify(h) # O(n), in place

heapq.heappush(h, 2) # O(log n)

smallest = heapq.heappop(h) # O(log n), returns 1

peek = h[0] # O(1) - the min is always index 0, no pop needed

heapq compares whatever you push using <, which means pushing a tuple compares it element-by-element, left to right. That is useful - it is how you attach a priority to a payload - and it is also a trap:

⚠

Un-orderable payloads crash the tuple trick

heapq.heappush(h, (priority, payload)) works only as long as no two priorities ever tie. If they do, Python moves on to compare payload directly, and a payload that has no < defined - two dicts, two dataclass instances without order=True, two arbitrary objects - raises TypeError at the least convenient possible moment, mid-run, on whichever input happens to have a duplicate priority. The fix is a middle tiebreaker field that is always comparable and always unique, such as an insertion counter:

counter = itertools.count()

heapq.heappush(h, (priority, next(counter), payload))

Ties on priority now break on counter, which is always distinct, so payload is never reached by the comparison.

Function	Cost	Does
heapify(list)	O(n)	Turns an existing list into a heap, in place.
heappush(h, x)	O(log n)	Appends then sifts up.
heappop(h)	O(log n)	Swaps last-to-root, shrinks, sifts down; returns the old root.
h[0]	O(1)	Peek the minimum without removing it.
heapq.nlargest(k, it)	O(n log k)	The k largest, without you managing a heap by hand.
heapq.nsmallest(k, it)	O(n log k)	The k smallest, same idea.

The one pattern worth internalizing on sight: "the k largest" is a size-k min-heap, which reads backward the first time you meet it.

Mnemonic

To keep the k largest, throw away the smallest - and a min-heap makes "the smallest" free to find. Push every value in; the moment the heap exceeds size k, pop it - which discards the current minimum of your candidate set. Whatever survives to the end is the k largest overall, and the heap's own root, at every point along the way, is the weakest member still standing - exactly the one you want to be able to evict in O(log k).

def k_largest(nums, k):

heap = []

for x in nums:

heapq.heappush(heap, x)

if len(heap) > k:

heapq.heappop(heap) # evict the current smallest of the k

return heap # k largest, in no particular order

7. What a heap is not

A heap is a narrow tool, and most of its bugs come from expecting it to be a wider one.

	Sorted array	BST	Heap
Find the min/max	O(1)	O(log n) average	O(1) - it is always the root
Remove the min/max	O(n) (shift)	O(log n) average	O(log n), always
Search an arbitrary value	O(log n)	O(log n) average	O(n) - no ordering rules out a subtree
Insert	O(n) (shift)	O(log n) average, O(n) worst	O(log n), always
In-order gives all elements sorted	yes, trivially	yes	no
Balance guarantee	n/a	none, unless self-balancing	always complete, by construction

• Not sorted. Reading a heap's array left to right is not reading the values in order - only heap[0] is guaranteed to be anything.
• Not a BST. There is no left < node < right invariant, so nothing supports a binary search once you leave the root.
• Not a general priority structure with fast arbitrary deletes. Removing "the element with value 8, wherever it is" is not a heap operation - you would have to find it first, which is the O(n) search this whole page keeps warning about. (A heap with an index map to support that is a real, more complex structure, not the one described here.)

Where to go next

• Range Query Trees - another tree packed into a plain array with index arithmetic, this time for range queries rather than a single running extreme.
• Tries - the other tree on this shelf that almost never gets drawn with TreeNode pointers in practice.
• Trees in the Wild - where heaps show up disguised as "priority queue" in scheduling, Dijkstra, and merging.