Heaps and Priority Queues
How a binary heap stores a priority queue in a plain array, why building one is O(n), and patterns that use it: kth largest, merging sorted lists, task priorities. Python heapq with measured counts.
A binary heap is a complete binary tree stored in an array where every parent is no larger than its children, so the minimum is always at index 0. It implements a priority queue with O(log n) push and pop and O(1) peek. Interviewers expect that building a heap from n items with heapify costs O(n), not O(n log n).
A heap is a binary tree stored in an array where every parent is no larger than its children, so the smallest item is always at index 0. Push and pop cost O(log n). Building a heap from n items costs O(n), not O(n log n): in a test of 100,000 numbers it took 1.65 comparisons per item against 2.27 for pushing one at a time.
- In an array-based binary heap, the node at index i has children at 2i + 1 and 2i + 2 and its parent at (i - 1) // 2.
- Binary heap push and pop each cost O(log n) because sift up and sift down follow one path through about log2(n) levels; peeking at the root is O(1).
- Building a heap with heapify is O(n): on 100,000 random floats heapify used 1.65 comparisons per item, versus 2.27 per item for 100,000 pushes.
- Finding the kth largest of n items with a min-heap of size k takes O(n log k) time and O(k) memory, since the root is the weakest of the current top k.
- Python's heapq provides only a min-heap, so a max-heap is usually built by pushing negated values.
- Searching a heap for a specific value is O(n), because a heap orders only parents and children, not siblings.
01What a priority queue promises
A priority queue is an abstract type with two main operations: insert an item with a priority, and remove the item with the best priority. A queue returns the oldest item and a stack the newest. A priority queue returns the most important one, whenever it arrived.
A sorted list would work but inserting into it is O(n). An unsorted list inserts in O(1) but finding the best is O(n). A binary heap balances the two: both operations are O(log n). Task schedulers, Dijkstra's shortest-path algorithm, and event simulations rely on it.
02The heap property and the array layout
A min-heap is a complete binary tree (every level full except possibly the last, filled left to right) where each parent is less than or equal to both children. Nothing is said about left versus right, so a heap is only partly ordered. What it guarantees is that the minimum is at the root.
Because the tree is complete, it fits in an array with no pointers. The node at index i has children at 2i + 1 and 2i + 2, and its parent is at (i - 1) // 2. Pushing 5, 3, 8, 1, 9, 2 in that order with Python's heapq gives the list:
import heapq
h = []
for x in [5, 3, 8, 1, 9, 2]:
heapq.heappush(h, x)
print(h) # [1, 3, 2, 5, 9, 8]Index 0 holds 1, the minimum. Its children at indexes 1 and 2 are 3 and 2, both larger. The list is not sorted, and it does not need to be.
03Push and pop: sift up, sift down
To push, put the new item at the end of the array and swap it upward while it is smaller than its parent (sift up). To pop, take the root, move the last item into the root slot, and swap it downward with its smaller child until the property holds (sift down).
Each move follows a single path from a leaf to the root or back, and a complete tree with n items has about log2(n) levels. So both operations are O(log n). Popping all n items in order is the heapsort idea. In my test of 100,000 random numbers, popping everything made about 1.53 million comparisons, close to n log2 n, and the output matched sorted().
04Building a heap in O(n)
If you already have all the items, call heapq.heapify(list) instead of pushing each one. It starts from the last parent and sifts each one down. Most nodes are near the bottom and move only a step or two, which is why the total work is linear.
I counted comparisons on 100,000 random floats by wrapping them in a class that increments a counter in __lt__:
heapify: 165,000 comparisons (1.65 per item)
100,000 pushes: 227,419 comparisons (2.27 per item)Both are linear for random data, and heapify is cheaper and has a guaranteed O(n) bound. The worst case for repeated pushes is O(n log n), for example when items arrive in descending order for a min-heap. Use heapify when the data is already in hand.
05Pattern 1: kth largest with a small heap
import heapq
def kth_largest(nums, k):
h = nums[:k]
heapq.heapify(h) # min-heap of the k largest so far
for x in nums[k:]:
if x > h[0]: # beats the smallest of the top k
heapq.heapreplace(h, x)
return h[0]
print(kth_largest([3, 2, 1, 5, 6, 4], 2)) # 5The heap holds at most k items, so memory is O(k) and time is O(n log k). That beats sorting everything (O(n log n)) when k is small, and it works on a stream you cannot store. The trick to remember is that you use a min-heap to find the largest items, because the root is the weakest member of the current top k and the first one to evict. For simple cases, heapq.nlargest(3, [5, 1, 9, 3, 7, 9, 2]) returns [9, 9, 7].
06Pattern 2: merging sorted lists, and priorities with tuples
import heapq
print(list(heapq.merge([1, 4, 7], [2, 5, 8], [3, 6, 9])))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]heapq.merge keeps one item from each list in a heap and always emits the smallest, so merging k sorted lists of total size n costs O(n log k). This is how external sorting combines sorted chunks from disk.
For tasks with priorities, push tuples:
import heapq
h = []
for pri, task in [(2, 'email'), (1, 'page oncall'), (3, 'report'), (1, 'disk full')]:
heapq.heappush(h, (pri, task))
print([heapq.heappop(h) for _ in range(4)])
# [(1, 'disk full'), (1, 'page oncall'), (2, 'email'), (3, 'report')]Tuples compare element by element, so equal priorities fall back to comparing the task. Here 'disk full' came out before 'page oncall' only because it sorts earlier alphabetically, not because it arrived later. If tasks cannot be compared, Python raises a TypeError on a tie. A common fix is (priority, counter, task) with an increasing counter, which also keeps first-come-first-served order among equals. heapq only offers a min-heap, so for a max-heap push negated values.
07What a heap cannot do
Searching for a specific value in a heap is O(n), because the order between siblings is unspecified. Removing or changing the priority of an arbitrary item is awkward for the same reason. Algorithms like Dijkstra handle this by pushing a duplicate entry with the new priority and ignoring stale entries when they are popped.
If you need ordered iteration, range queries or lookups by key as well, use a balanced search tree instead. A heap is the right structure when you only ever ask for the next best item.
08Common interview questions
Q: Complexity of push, pop and peek?
A: Push and pop are O(log n). Peek at the root is O(1).
Q: Why is building a heap O(n)?
A: Most nodes are near the leaves and sift down only a short distance. The total work sums to a linear bound.
Q: How do you find the k largest elements in a stream?
A: Keep a min-heap of size k. Replace the root whenever a larger item arrives. Time O(n log k), memory O(k).
Q: How do you get a max-heap in Python?
A: Push negated values, or wrap items in a class with reversed comparison.
Q: Heap versus sorted array?
A: A sorted array gives O(1) access to the best item but O(n) inserts. A heap gives O(log n) for both.
Q: Is a heap sorted?
A: No. Only the parent-child order is guaranteed.