A tree that only promises one thing: the smallest item is at the top. That weaker guarantee is what makes insert and extract cost O(log n) — and it is the engine inside Dijkstra and A*.
Controls
Tree and Array Are the Same Thing
step 0
Backing array — no pointers needed
Insight
A heap is a complete binary tree where every parent beats its children. Siblings are unordered — that is the weakness which buys the speed.
Weaker ordering than a BST, and that is exactly the point.
The problem it solves
A heap is a complete binary tree obeying one rule: every parent is smaller than both its children (a min-heap) or larger than both (a max-heap). It says nothing about siblings — the tree is only partially ordered.
Why Partial Ordering Is Better Here
A BST fully sorts its data, which costs effort to maintain. A heap only guarantees the extreme value sits at the root. If all you ever ask is "what is the smallest item?", full sorting is wasted work.
That weaker promise makes the structure cheap to maintain: O(1) to read the root, O(log n) to insert or remove it. Note that heaps are terrible at searching for an arbitrary value — that is O(n), because the ordering gives you no guidance below the root.
An Array Pretending to Be a Tree
Heaps need no pointers at all. Because the tree is complete — every level full except possibly the last, filled left to right — positions can be computed with arithmetic:
Watch the tree and the array update together as you insert. They are the same structure drawn two ways. This makes heaps compact and cache-friendly — a real advantage over pointer-based trees.
Sift Up and Sift Down
Insert — place the new value at the end of the array (the only spot that keeps the tree complete), then sift up: repeatedly swap with the parent while it is out of order. At most one swap per level, so O(log n).
Extract root — take the root, move the last element into its place, then sift down: repeatedly swap with the smaller child until order is restored. Again O(log n).
The swap counter shows this: even with 15 elements, no operation needs more than about 4 swaps.
Priority Queues Everywhere
A priority queue serves the highest-priority item rather than the oldest, and a heap is how it is almost always implemented. That makes heaps quietly essential:
Dijkstra and A* repeatedly need "the unvisited node with the smallest distance" — exactly a min-heap extract. Both of your existing pathfinding apps depend on this.
Heap sort builds a heap and extracts repeatedly: O(n log n) with O(1) extra space.
Top-k problems — keep a size-k heap and you find the largest k items in O(n log k) without sorting everything.
Schedulers and event simulations — always process the next-earliest event.
A tree that keeps its smallest element on top
A binary heap is a complete binary tree with one rule — the heap property:
Min-heap: every parent is less than or equal to its children. Max-heap: every parent is greater than or equal to its children.
Note what the rule does not say: siblings are unordered, and the tree is not sorted. The only guarantee is that the smallest (or largest) element is at the root, which is exactly what a priority queue needs.
That weaker guarantee is what makes a heap fast. Maintaining full sorted order on every insertion would cost O(n); maintaining only the parent-child relation costs O(log n).
Operation
Heap
Sorted array
Unsorted array
Find minimum
O(1)
O(1)
O(n)
Insert
O(log n)
O(n)
O(1)
Remove minimum
O(log n)
O(n) or O(1) at the end
O(n)
Build from n items
O(n)
O(n log n)
O(1)
The last row is worth noting: building a heap from an existing list is O(n), not O(n log n) — heapq.heapify does it in place by sifting down from the middle.
Stored as an array, not as nodes
A heap needs no pointers. Because the tree is complete, the structure is implicit in the array indices:
parent of i = (i − 1) // 2 children of i = 2i + 1 and 2i + 2
So [1, 3, 6, 5, 9, 8] represents a tree whose root is 1, with children 3 and 6, and so on. No allocation per node, and excellent cache behaviour because the whole structure is contiguous.
The two operations that maintain the property:
Sift up (after insertion). Add the element at the end, then swap it with its parent while it is smaller. At most log n swaps.
Sift down (after removing the root). Move the last element to the root, then swap it with its smaller child while it is larger. At most log n swaps.
Both walk one path from root to leaf, which is why both are O(log n).
It is a min-heap only. For a max-heap, negate the values on the way in and out — heappush(h, -x) and -heappop(h). There is no max-heap variant.
Priorities go in tuples.heappush(h, (priority, item)) sorts by priority. If two priorities tie, Python compares the second element, so items must be comparable — or push a counter as a tiebreaker:
That counter pattern is worth memorising; the alternative is an occasional TypeError in production when two priorities happen to match.
Partial order is the point, not a compromise
A heap is often introduced as a tree that is only sort-of sorted, which sounds like a weaker version of something better. It is the opposite: the ordering it does NOT maintain is exactly the work it does not have to do, and that shows up the moment you compare it with keeping a list sorted.
example_01.pyPython
import heapq
import random
import time
# A heap only guarantees parent <= child. Siblings are unordered, and
# the array is emphatically not sorted:
h = []
for x in [5, 3, 8, 1, 9, 2, 7]:
heapq.heappush(h, x)
print("heap array:", h)
print("sorted: ", sorted(h))
print("smallest is at index 0:", h[0] == min(h))
# Every level down is a valid heap too, which is the invariant:
def check(a):
return all(a[p] <= a[c]
for c in range(1, len(a))
for p in [(c - 1) // 2])
print("parent <= child everywhere:", check(h))
# The array IS the tree. Node i has children 2i+1 and 2i+2 -- no pointers,
# no nodes, no allocation:
print()
for i in range(len(h) // 2):
kids = [h[j] for j in (2 * i + 1, 2 * i + 2) if j < len(h)]
print(" h[%d] = %d -> children %s" % (i, h[i], kids))
# Now the comparison that matters. A sorted list also gives you the
# minimum in O(1) -- it is just list[0]. The difference is what INSERT
# costs, and that is where the partial order pays.
def timed(f, n):
t0 = time.time(); f(n); return (time.time() - t0) * 1000
def with_heap(n):
q, rng = [], random.Random(1)
for _ in range(n):
heapq.heappush(q, rng.random())
while q:
heapq.heappop(q)
def with_sorted_list(n):
import bisect
q, rng = [], random.Random(1)
for _ in range(n):
bisect.insort(q, rng.random()) # O(log n) to find, O(n) to shift
while q:
q.pop(0)
print()
print("%8s %14s %18s" % ("n", "heap (ms)", "sorted list (ms)"))
for n in (2000, 4000, 8000):
print("%8d %14.1f %18.1f" % (n, timed(with_heap, n),
timed(with_sorted_list, n)))
# The sorted list has to keep a total order it was never asked for. The
# heap maintains only the parent-child relation, which is one path from
# the insertion point to the root -- log n comparisons and no shifting.
#
# The classic use is scheduling: always take the most urgent job, and
# keep adding jobs while you work.
jobs = [(3, "write report"), (1, "server on fire"), (2, "review PR"),
(5, "reorganise inbox"), (1, "customer down")]
pq = []
for pri, name in jobs:
heapq.heappush(pq, (pri, name))
print()
print("handling in priority order:")
while pq:
pri, name = heapq.heappop(pq)
print(" [p%d] %s" % (pri, name))
if name == "server on fire":
heapq.heappush(pq, (1, "write incident postmortem"))
print(" (a new p1 job arrived mid-queue)")
# The new p1 job jumped ahead of everything with a lower priority, and
# nothing had to be re-sorted to make that happen. A sorted list would
# have shifted every element after the insertion point; the heap moved
# one item up one short path.
Output
Try it yourself
Insert a value smaller than the root. Watch it bubble all the way to the top — one swap per level, never more.
Insert a large value. It stays near the bottom with no swaps at all — the average insert is far cheaper than the worst case.
Extract the root repeatedly. The last element jumps to the top and sinks back down. Values come out in sorted order — that is heap sort.
Compare the array with the tree as you go. Index 0 is the root; index i's children are at 2i+1 and 2i+2, always.
Switch to a max-heap. The same machinery runs with the comparison flipped — that is the only difference between the two.
Where that leaves you
A heap keeps only the extreme value ordered, and that weaker guarantee is what makes it fast: O(1) peek, O(log n) insert and extract, in a pointer-free array. Whenever an algorithm repeatedly asks for the smallest or largest remaining item, a heap is the answer.
What heaps are used for
Dijkstra's algorithm and A*. The priority queue of nodes by tentative distance is a heap, and it is what gives those algorithms their log factor rather than a linear scan.
Top-k problems. To find the k largest of n items, keep a min-heap of size k: push each item, and pop when the heap exceeds k. O(n log k) time and O(k) space, against O(n log n) for sorting everything. When k is small and n is huge, this is the difference between feasible and not.
def top_k(items, k):
h = []
for x in items:
heapq.heappush(h, x)
if len(h) > k:
heapq.heappop(h) # discard the smallest
return sorted(h, reverse=True)
Heap sort. Heapify, then repeatedly extract the minimum. O(n log n) guaranteed, in place, and not stable.
Merging sorted sequences.heapq.merge performs a k-way merge lazily, which is how external sorting combines sorted runs.
Task schedulers and event simulation. Process the earliest-deadline or earliest-timestamp item next.
Median maintenance. Two heaps — a max-heap of the lower half and a min-heap of the upper half — give the running median of a stream in O(log n) per element.
Huffman coding. Repeatedly combine the two least frequent symbols, which is a priority queue by construction.
The limitation: no efficient search or update
A heap answers "what is the smallest?" and nothing else. Finding an arbitrary element requires scanning — O(n) — because siblings are unordered.
That matters for algorithms that want to decrease a key: Dijkstra ideally updates a node's priority in place, and a binary heap cannot locate that node quickly. The standard workaround is lazy deletion — push a new entry and skip stale ones when popped — which is why Dijkstra implementations carry that check.
If you need both priority access and lookup, the usual answer is a heap plus a dictionary from item to its position, maintained together. That is more code and it is what a proper indexed priority queue provides.
Need
Structure
Smallest or largest, repeatedly
Heap
Sorted iteration
Sorted list, or a balanced tree
Lookup by key
Hash table
Range queries
Balanced tree
Priority plus lookup
Heap plus an index dictionary
Questions people ask
Is a heap sorted? No. Only the root is guaranteed to be the extreme value; siblings are unordered.
How do I get a max-heap in Python? Negate the values, or store (-priority, item) tuples.
Why is building a heap O(n) rather than O(n log n)? Sifting down from the middle backwards does less work at the deep levels, and the sum works out to O(n).
What is the difference from queue.PriorityQueue? It wraps heapq with locking for thread safety, which costs performance. Use heapq in single-threaded code.
Can a heap have duplicates? Yes, without any problem.
Is heap sort used in practice? Rarely on its own — quick sort is faster in the average case. It appears as introsort's fallback, providing the worst-case guarantee.
Recap in one screen
A heap keeps the extreme element at the root; parents are ordered against children and siblings are not.
It is stored as a plain array, with children at 2i+1 and 2i+2 — no pointers, good cache behaviour.
Push and pop are O(log n); finding the minimum is O(1); building from a list is O(n).
Python's heapq is a min-heap only, and tuple priorities need a tiebreaker to avoid comparing payloads.
Ideal for priority queues, top-k with O(k) memory, k-way merges, schedulers and running medians.
A worked heap trace
Building a max-heap from [3, 9, 2, 1, 4, 5] by sifting down from the middle backwards makes the O(n) build concrete.
Indices 5, 4, 3 are leaves and need nothing. Start at index 2:
Step
Node
Children
Action
Array
Start
—
—
—
[3, 9, 2, 1, 4, 5]
i = 2
2
5 (index 5)
Swap
[3, 9, 5, 1, 4, 2]
i = 1
9
1, 4
Already largest
[3, 9, 5, 1, 4, 2]
i = 0
3
9, 5
Swap with 9
[9, 3, 5, 1, 4, 2]
i = 0 cont.
3
1, 4
Swap with 4
[9, 4, 5, 1, 3, 2]
Final heap: [9, 4, 5, 1, 3, 2]. The root is the maximum, every parent exceeds its children, and the siblings are unordered — 4 sits before 5, which is perfectly valid.
Extracting repeatedly then gives the sorted order: swap the root with the last element, shrink, sift down. That is heap sort.
Two things this trace demonstrates. The build genuinely does little work — three sift operations for six elements, most of them trivial. And the array's final layout looks unsorted, which is the point: a heap is not a sorted structure, only a partially ordered one.
Where to practise this
The three questions that come up once a heap is on the table:
A binary heap written from scratch on a plain list, then the same job handed to heapq. The point of the first half is that the tree is entirely imaginary — there are no nodes and no pointers.
heap.pyPython 3
# A min-heap: the smallest item is always at index 0.
import heapq
class MinHeap:
def __init__(self):
self.a = []
def push(self, x):
self.a.append(x) # put it at the end...
i = len(self.a) - 1
while i > 0: # ...and bubble it up
parent = (i - 1) // 2
if self.a[parent] <= self.a[i]:
break
self.a[parent], self.a[i] = self.a[i], self.a[parent]
i = parent
def pop(self):
smallest = self.a[0]
last = self.a.pop()
if self.a:
self.a[0] = last # move the last item to the root...
i = 0
while True: # ...and sift it down
left, right = 2 * i + 1, 2 * i + 2
child = left
if right < len(self.a) and self.a[right] < self.a[left]:
child = right
if child >= len(self.a) or self.a[i] <= self.a[child]:
break
self.a[i], self.a[child] = self.a[child], self.a[i]
i = child
return smallest
h = MinHeap()
for x in [5, 3, 8, 1, 9, 2]:
h.push(x)
print(f"push {x} -> {h.a}")
print()
print("popped in order:", [h.pop() for _ in range(6)])
print()
print("The list IS the tree. Index i's children are 2i+1 and 2i+2:")
tree = [1, 3, 2, 5, 9, 8]
for i, value in enumerate(tree):
kids = [tree[j] for j in (2 * i + 1, 2 * i + 2) if j < len(tree)]
print(f" index {i} = {value:>2}, children {kids}")
# --- the same thing, using the standard library ------------------------
print()
tasks = [(3, "write tests"), (1, "fix the outage"), (2, "review PR")]
heapq.heapify(tasks) # O(n), not O(n log n)
while tasks:
priority, name = heapq.heappop(tasks)
print(f" priority {priority}: {name}")
# Top-k without sorting the whole list.
data = [17, 4, 92, 8, 55, 23, 71, 3]
print()
print("3 largest:", heapq.nlargest(3, data), "- O(n log k), not O(n log n)")
Output
How the code works
parent = (i - 1) // 2The tree exists only as arithmetic. A node at index i has its parent at (i-1)//2 and children at 2i+1 and 2i+2 — no pointers are stored, and none are needed.
if self.a[parent] <= self.a[i]: breakA heap is a much weaker promise than a sorted list: each parent beats its own children, and nothing is claimed about siblings. That weakness is why push and pop cost O(log n) instead of O(n).
last = self.a.pop(); self.a[0] = lastPopping the root leaves a hole, and the only item that can be removed without leaving a second hole is the last one. Moving it to the root and sifting down repairs the heap in one pass.
if right < len(self.a) and self.a[right] < self.a[left]:Always sift towards the smaller child. Choosing the larger one makes it a valid-looking heap that returns wrong answers — a quiet bug rather than a crash.
heapq.nlargest(3, data)Keeps a heap of size k rather than sorting everything: O(n log k). For “top 10 of a billion” that is the difference between practical and not.
Change one thing
Print h.a after all the pushes. It is not sorted — only a[0] is guaranteed, and expecting more is the usual misunderstanding.
Flip both comparisons to build a max-heap. Python's heapq has no max version, so real code pushes -value instead.
Push (priority, task) tuples where two priorities tie and the second item is not comparable. The TypeError is why production code pushes a counter as a tie-breaker.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
In an array-backed heap, the children of index i are at:
The tree is arithmetic, not structure. No node objects and no pointers are stored at all.
After several pushes, the underlying list is:
A heap promises each parent beats its children and nothing about siblings. Expecting more is the usual misunderstanding.
heapq.nlargest(k, data) is O(n log k) rather than O(n log n) because it:
For "top 10 of a billion" that is the difference between practical and not.
Cheat sheet
Heaps and Priority Queues
A tree that only promises one thing: the smallest item is at the top. That weaker guarantee is what makes insert and extract cost O(log n) — and it is the engine inside Dijkstra and A*.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.