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).
Using it in Python
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappop(h) # 1 - always the smallest
nums = [5, 1, 8, 3, 9]
heapq.heapify(nums) # O(n), in place
heapq.nlargest(3, nums) # [9, 8, 5]
heapq.nsmallest(3, nums) # [1, 3, 5]
Two practical points about Python specifically.
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:
import itertools
counter = itertools.count()
heapq.heappush(h, (priority, next(counter), task)) # never compares task
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.
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.