Python heaps with heapq

Why it matters

A queue hands out items in the order they arrived. Real work often needs a different order. An emergency room treats the most urgent patient first, not the one who arrived earliest. A cloud scheduler runs the most important job first. A route planner always expands the cheapest path found so far. In each case you want the item with the highest priority, and you want it quickly, even while new items keep arriving.

A heap is the structure built for that job. It removes the item with the best priority in O(log n) time, and it reads that item in O(1). Python's standard library has a module named heapq that provides a heap on top of an ordinary list. Many interview problems that look like sorting or searching turn out to be heap problems in disguise, so this lesson teaches the idea, the heapq functions, the tricks for custom orders and the standard patterns.

Start from the problem: keeping the smallest item

Suppose you have a list of numbers that keeps changing, and you need the smallest number at any moment. You could sort the list every time a number arrives, which costs O(n log n) per change. You could scan the whole list for the smallest number, which costs O(n) per question. Neither is fast enough when the list has a million numbers and changes all day.

A heap gives a better trade. It does not keep the whole list in order. It keeps only the one fact you need most: the smallest item is at the top. The rest of the structure is just enough order to keep that fact true after every change. Adding an item and removing the top each cost O(log n), which for a million items is about twenty steps.

An analogy: the emergency room

Picture a hospital waiting room. Patients arrive at different times, but the doctor does not see them in arrival order. The nurse sorts them by urgency. A patient with a broken arm waits behind a patient with chest pain, even if the arm arrived first. When the doctor is free, the most urgent patient in the room is called. Each new arrival is placed by urgency, not by the time of arrival.

A heap works the same way. Each item has a priority. When you ask for the next item, you get the one with the highest priority. In heapq, "highest priority" means the smallest value, so the number 1 is treated as more urgent than 5.

Your first heap

Here is a short program. The heapq functions work on an ordinary list, so the list you pass in is the heap. Read the output carefully, because it contains a surprise.

The output is:

inside: [1, 3, 8, 5]
peek: 1
poll order: 1 3 5 8

The first line shows the list while it is held as a heap. The numbers are not in sorted order. 1, 3, 8, 5 is a valid heap, but it is not a sorted list, because 8 comes before 5. The printout shows the internal list of the heap, not the order in which you would take items out. Only repeated heappop calls give you items in sorted order.

The line heap[0] looks at the top, which is the smallest value, 1, without removing it. The heappop calls remove the top each time, and each removal reorganises the heap so the next smallest value moves to the top. The while loop keeps popping until the heap is empty, and the printed order is sorted.

Note that heapq has no class. You call heapq.heappush(heap, value) and heapq.heappop(heap) on a list you created yourself. The list must start empty, or hold a valid heap that you made with heapq.heapify.

How a binary heap works

The structure behind heapq is a binary heap. Think of it as a family tree in which every parent is smaller than or equal to each of its children. The root, the top of the tree, is always the smallest item. Each node has at most two children. The tree is kept as balanced as possible, filled one level at a time, from left to right.

The good news is that a heap is stored in an ordinary list, the same row of slots you saw in the first lesson of this module. You do not need pointers. The rule is about positions. In a list that starts at index 0, the parent of index i sits at index (i - 1) // 2, rounded down. The children of index i sit at 2 * i + 1 and 2 * i + 2. Because of these formulas, the tree shape is known from the list length alone.

Picture the four values 1, 3, 8 and 5 as a tree. The 1 is the root. Its children are 3 and 8. The 5 is the child of 3. In the list, the values sit at indexes 0, 1, 2 and 3, in that order: [1, 3, 8, 5]. The value at index 3 is the child of the value at index 1, because (3 - 1) // 2 is 1.

The heappush function puts the new item at the end of the list, which is the next free spot in the tree. Then it compares the item with its parent. If the item is smaller, they swap, and the comparison repeats one level higher. The item keeps moving up until its parent is smaller or until it reaches the root. This is called sift up. It takes at most one swap per level, and a tree with n items has about log2(n) levels, so heappush costs O(log n).

The heappop function takes the root out. It moves the last item in the list to the root, and then the item moves down by swapping with its smaller child. If the child is smaller, they swap, and the item keeps moving down until it has no smaller child. This is called sift down. It also takes about one swap per level, so heappop costs O(log n).

The access heap[0] just reads the root, so it costs O(1). Searching for an arbitrary value is slow, because the heap does not keep the other values in order. Checking whether a value is in the heap with in costs O(n), which is one of the first facts to remember.

Cost table

The row for heapify surprises many students. Pushing n items one at a time costs O(n log n). Building the heap from a whole list in one pass with heapify costs O(n). Use heapify when you already have all the items in a list.

Changing the order: max-heap and tuples

A plain heapq heap is a min-heap, which means the smallest value is served first. Python has no built-in max-heap option. The standard trick is to store the negative of each number. The smallest negative number is the largest original number, so the min-heap serves the largest value first.

The output is:

9 7 4 1

The loop pushes the negative of each number. The values in the heap are -9, -4, -7 and -1, and the smallest of them is -9. Popping gives -9, and the minus sign turns it back into 9 when the program prints it.

For your own kind of item, you have two choices. The first is a tuple. Python compares tuples one item at a time, from left to right, so a tuple of (priority, name) sorts by priority first and by name when priorities tie. The program below uses tuples to rank tasks. A smaller priority number is more urgent.

The output is:

1 deploy
2 review
3 backup
3 email

The tuple (3, "backup") comes before (3, "email"), because the priorities tie and the names are compared alphabetically. Without the second item in the tuple, two equal priorities would come out in no guaranteed order. The unpacking line priority, name = heapq.heappop(queue) splits the tuple back into its two parts.

The second choice is a dataclass (a class whose fields Python sets up for you) with order=True. Python then compares two objects by their fields, in the order the fields are written. The class in the next example is a small record. Its priority field is compared first, and its name field second.

The output is:

Task(priority=1, name='deploy')
review

The heapify call turns the list into a heap in one pass. The first heappop returns the whole Task object with the smallest priority. The second returns the next one, and .name reads its name field.

Top-k: the most useful heap pattern

The top-k pattern answers questions such as "the 3 largest scores" or "the kth largest number". The obvious approach is to sort everything, which costs O(n log n). The heap approach costs O(n log k), which is much cheaper when k is small compared with n.

The trick is easy to get backwards. To keep the k largest values, use a min-heap of size k. Add each value. If the heap grows beyond k, remove the smallest value in it, because the smallest of the current winners is the first one to lose its place. When every value has been seen, the heap holds the k largest, and its top is the kth largest value. This is why a min-heap, not a max-heap, is the right tool for keeping the largest values.

The program below reads n and k, then n numbers, and prints the k largest in descending order. Save it as a file. When it asks for input, type this, one line at a time:

7 3
5 1 9 3 9 7 2

import heapq
 
n, k = map(int, input().split())
values = list(map(int, input().split()))
 
heap = []
for value in values[:n]:
    heapq.heappush(heap, value)
    if len(heap) > k:
        heapq.heappop(heap)
 
print(" ".join(str(v) for v in sorted(heap, reverse=True)))

The output is:

9 9 7

Trace the first few numbers. The heap starts empty. The numbers 5, 1 and 9 go in, so the heap holds {1, 5, 9}, which is exactly k. The number 3 goes in, and the heap now holds four items, which is more than k. The smallest item, 1, is removed, leaving {3, 5, 9}. Then 9 arrives and the smallest, 3, leaves. Then 7 arrives and 5 leaves. Then 2 arrives and 2 itself is the smallest, so it leaves at once. The heap ends with {7, 9, 9}, the three largest values. The last line sorts them in descending order to print them.

Python's standard library also has a function for this. heapq.nlargest(k, values) returns the k largest values in descending order, and heapq.nsmallest(k, values) returns the k smallest in ascending order. It does the same work as the loop above. Writing the loop is still worth it once, because it shows the reason for the min-heap.

The top-k pattern has close relatives that appear often in interviews:

• Top k frequent words. Count the words with a Counter from the collections module, then keep a min-heap of size k ordered by count.
• Merge k sorted lists. Put the head of each list in a min-heap, pop the smallest, and push the next item from that same list.
• Running median. Use two heaps, a max-heap for the smaller half and a min-heap for the larger half.

Merge k sorted lists

Suppose you have several sorted lists and need one sorted list of all their items. Comparing every list's front item each time is slow when there are many lists. A heap keeps the smallest front item of all the lists at the top, so each step is O(log k), where k is the number of lists.

The program below uses three sorted lists. Each heap entry is a tuple of three values: the value, the number of the list it came from, and its position inside that list. Tuples compare by their first item, so the heap orders them by value. When an entry leaves the heap, the program pushes the next value from the same list, which keeps the heap holding one front item per list.

The output is:

[0, 1, 2, 3, 4, 8, 9, 10]

The heap starts with the front item of each list: 1, 2 and 0. The first pop removes 0, which is the front of the third list, so the program pushes 8 from that list. The next smallest is 1, then 2 from the second list, which brings in 3, and so on. Every value is pushed and popped exactly once, and the heap never holds more than one item per list.

The standard library has this as heapq.merge(*lists), which returns the merged values one at a time, lazily. The line print(list(heapq.merge(*lists))) prints the same list as the program above. Write the loop once to understand it, then use heapq.merge in real code.

The total cost is O(N log k), where N is the total number of items and k is the number of lists. Compare this with copying everything into one list and sorting it, which costs O(N log N). The heap version wins when k is small.

Running median with two heaps

The median is the middle value of a sorted list. For an odd count it is the middle item. For an even count it is the average of the two middle items. If numbers keep arriving, you want the median after each arrival without sorting from scratch each time.

The trick is to split the numbers into two halves. The lower half lives in a max-heap, so its largest value is at the top, right at the middle. Python has no max-heap, so the lower half stores negated numbers in a min-heap, and the top of that heap is the negative of the largest value. The upper half lives in a min-heap, so its smallest value is at the top, also right at the middle. The two tops give the median. The sizes must differ by at most one, so the middle is always reachable.

The program below runs the numbers 5, 15, 1 and 3 one at a time. After each number it prints the median with one decimal place.

The output is:

5.0
10.0
5.0
4.0

To read the numbers from the keyboard instead, replace the numbers line with numbers = [int(part) for part in input().split()] and type 5 15 1 3 as the input.

Trace the four numbers. The first number, 5, goes to the lower half, so the median is 5.0. The second, 15, is larger than the lower top, so it goes to the upper half. Both halves now hold one number, so the median is the average of 5 and 15, which is 10.0. The third number, 1, is not bigger than the lower top, so it also goes to the lower half. The lower half now holds 1 and 5, and the upper half holds 15. A difference of one is allowed, and the lower half's largest value, 5, is the median: 5.0. The fourth number, 3, goes to the lower half, which now holds 1, 3 and 5. That is two more than the upper half, so the largest of the lower half, 5, moves to the upper half. The lower half is 1 and 3, and the upper half is 5 and 15. Both halves have two numbers, so the median is (3 + 5) / 2, which is 4.0.

The format text :.1f prints a number with one digit after the decimal point. Each new number costs O(log n) for the heap operations. Finding the median costs O(1), because both tops are just read. Sorting the whole list after every number would cost O(n log n) per number, so the two-heap version is far faster.

Debugging walkthrough: a heap that will not compare

Here is a bug that a beginner meets as soon as they store records in a heap. A program stores pairs in a heap, and the pairs look like this:

import heapq
 
heap = []
heapq.heappush(heap, (2, {"name": "email"}))
heapq.heappush(heap, (2, {"name": "backup"}))

Pushing the first pair is fine. Pushing the second pair compares the two tuples. The first items tie, both being 2, so Python compares the second items, which are dictionaries. Dictionaries have no order, so the comparison fails:

TypeError: '<' not supported between instances of 'dict' and 'dict'

Read the message in two steps. The TypeError names the kind of problem: two values were used with an operator they do not support. The text inside the quotes names the operator, <, and the two types, dict and dict. The heap needs < to place items, so it failed on the second push.

The fix is to make sure the tuple never reaches the dictionary. Put a value that always differs in the second position, such as a counter, and keep the dictionary in the third position. The next section shows the counter, which also solves a different problem.

A similar error happens with mixed types. Pushing None into a heap that holds numbers raises '<' not supported between instances of 'NoneType' and 'int'. The fix is the same: keep one type in each heap, and do not put None in it.

Ties and fairness

Equal priorities have no guaranteed order in a heap. Python compares the next field of a tuple only when the first fields tie, and the heap itself does not keep the order of arrival. In a real system that can be unfair. Suppose two support tickets have the same priority. Without a tie-break, either one may be served first, and a customer may wait longer than another with the same urgency.

The fix is a counter that never repeats. The function itertools.count() makes numbers 0, 1, 2 and so on. A tuple of (priority, arrival number, name) serves the earlier arrival first among equal priorities:

The output is:

['1 deploy', '2 review', '3 email', '3 backup']

The email task arrived before the backup task, so it comes first among the two priority-3 tasks. The counter also means the tuple never reaches a comparison that would fail on the name or the payload, because the counter always differs.

Another fairness problem is starvation. If high-priority items keep arriving, a low-priority item may never reach the top. A common fix is aging: raise an item's priority a little each time it waits. Aging is a change to the priority value, so it runs into the rule from the next section, which is to remove, change and re-add, or to use lazy deletion. Explain starvation and aging in plain words when you describe a scheduler, because the interviewer usually wants to hear that you thought about waiting time, not only about speed.

Changing priorities: two fixes

A heap cannot change an item in place. If a document's priority changes, the heap keeps the old entry where it is until something moves it. There are two standard fixes.

The simple fix is to remove the item, change it, and add it back. Removing an arbitrary item from a heap costs O(n), because the program must find the item first. You would also need to rebuild the heap with heapify. So this fix is fine for a few changes and slow for many.

The second fix is lazy deletion. You never remove the old entry. You add a new entry with the new priority, and you record which entry is current. When an entry reaches the top, check whether it is still current. If it is stale, throw it away and pop again. Each entry is added once and removed at most once, so the cost stays O(log n) per operation, plus the stale entries that get discarded. Dijkstra's shortest-path algorithm uses this trick, and you will meet it in the graph modules.

The module assignment cancels a waiting document from the middle of the heap, which needs one of these fixes. Choose one of the two fixes and say why. Lazy deletion is the better choice when there are many changes, and the simple fix is fine for a handful.

Heaps against sorting: the cost in numbers

Choosing a heap over a sort is a cost decision, so it helps to see rough numbers. Sorting a million numbers costs about n times log2(n) comparisons, which is roughly 20 million. Finding the top three with a heap of size 3 costs about n times log2(3) comparisons, which is roughly 1.6 million. The heap does about a twelfth of the work. The numbers are rough, because real comparisons take different amounts of time, but the ratio explains why the top-k pattern matters.

The advantage shrinks as k grows. A heap of size half a million costs about as much as a sort, so at that size, sort the data instead. In Python, sorted is written in C and is very fast, so the heap wins only when k is small.

Popping a heap until it is empty also sorts the data. That idea is called heap sort, and its cost is O(n log n) in every case. In practice Python's sorted is faster on ordinary lists, but heap sort shows what the heap really is: a machine that hands out the next smallest item quickly.

Heap questions in interviews

Heap questions usually arrive in one of three forms. The first asks for the kth largest item or the k most frequent items. Answer with a heap of size k, and state the cost: O(n log k). The second asks you to merge several sorted sources. Answer with a heap that holds the front item of each source, and state the cost: O(N log k), where N is the total count. The third asks for the median of a stream of numbers. Answer with two heaps, a max-heap for the lower half and a min-heap for the upper half, and state the cost: O(log n) per number. In Python, say that the max-heap is a min-heap of negated values.

Interviewers then ask follow-up questions. If they ask what happens when k is close to n, the honest answer is that sorting becomes just as good, so the heap saves little. If they ask what happens when items arrive faster than you can process them, the heap still works one item at a time, and you should say that its memory is bounded by k or by the two halves. Prepare one sentence for each follow-up before the interview, so you do not have to invent it under pressure.

Common mistakes

Expecting sorted printing. print(heap) shows the internal list, which is partly ordered. Only repeated heappop calls give sorted order.

Reaching for a max-heap that does not exist. heapq is a min-heap only. Store negated numbers, or use a key that reverses the order.

Negating a value that is not a number. A negated tuple or string does not do what you want. Put the negation on the number part of the item.

Mutating an item after it is added. The heap does not notice the change, and later pops can come out in the wrong order. Remove the item, change it and add it again.

Pushing None or mixed types. A heap compares items to place them. A None next to a number raises TypeError.

Assuming equal priorities keep their arrival order. The heap does not promise that. If order among equal priorities matters, add a counter as a tie-breaker.

Using the wrong heap for top-k. To keep the largest k values, use a min-heap of size k. A max-heap of size k puts the largest value at the top, but the weakest winner sits somewhere below, where a single pop cannot reach it.

Popping an empty heap. heapq.heappop([]) raises IndexError: index out of range. Check if heap: first, the same way you check a stack.

Variations and edge cases

An empty heap has no top. Reading heap[0] raises IndexError: list index out of range. Check if heap: before you read the top, just as you did with stacks and queues.

A single item is the simplest case. heap[0] and heappop both return it, and the heap is empty afterwards.

Duplicates are allowed. Equal values sit in the heap with no guaranteed order among them. For numbers this does not matter. For records with other fields, use a counter as a tie-breaker.

For top-k with k bigger than n, the heap never grows past n items, so every value is kept. Your code should still return a sensible answer, such as the whole data sorted, rather than failing.

The tuple can hold any fields. You can sort by distance, then by name, then by date. Put the fields in the order of importance, and negate a number field to flip its order.

Interview-style and real-world uses

Interviewers use heaps to test whether you recognise a pattern from the wording. If the question asks for "the k largest", "the k most frequent", "the next smallest" or "merge sorted streams", think of a heap before you think of sorting. Then say why: the heap keeps only what you need, so the cost depends on k instead of n.

Be ready for the cost answer. The top-k solution is O(n log k) time and O(k) space. The merge of k lists is O(N log k) time. The running median is O(log n) per number. Practise saying these in one breath, with the reason for each log.

In real software, heaps run much of the scheduling. An operating system chooses the next process to run from a priority queue. A download manager chooses the next chunk to fetch. A shortest-path algorithm, which you will meet in the graph modules, keeps its frontier in a heap so it always expands the cheapest node next. When a program must always work on the most urgent item and new items keep arriving, a heap is the first structure to reach for.

Practice

1. Print the numbers [9, 4, 7, 1] in descending order using a heap. Use negated values.
2. Find the 3rd smallest element of [7, 10, 4, 3, 20, 15]. Use a max-style heap of size 3, which you build with negated values, and explain why that works.
3. Why does the kth-largest solution use a min-heap rather than a max-heap?
4. Write a sort key or a tuple for pairs (id, score) that serves the highest score first and breaks ties by the smaller id.
5. Build a heap of words with heapq, then pop all of them. Print the words in alphabetical order, and explain why the printing order matches.
6. Write a function top_k_frequent(values, k) that returns the k values that appear most often. Use a Counter for counts and a heap of size k. Do not worry about tie order.
7. Use a heap to find the smallest number from 1 to 10 that is not in the list [5, 3, 9]. Explain how the heap helps, and say whether a set would be simpler.
8. Explain, in your own words, why the cost of heappop is O(log n) and not O(n).
9. Write a function that merges two sorted lists using a heap. Explain whether the heap is worth it for two lists.
10. A scheduler stores tasks as (due, name) tuples, where a smaller due means the task is more urgent. Write the code that pushes three tasks and pops them in order. Say what happens to two tasks with the same due time, and add a counter so the order is predictable.

Exercise 1. Show the answer:

import heapq
 
heap = []
for v in [9, 4, 7, 1]:
    heapq.heappush(heap, -v)
print(" ".join(str(-heapq.heappop(heap)) for _ in range(4)))

The output is 9 7 4 1.

Exercise 2. Show the answer: the answer is 7. Keep a heap of the three smallest values seen so far, stored as negated numbers, so the largest of those three is at the top. After 7, 10 and 4 the heap holds 10, 7 and 4. After 3 the heap grows to four, so the largest, 10, is removed, leaving 7, 4 and 3. After 20 it is removed at once, and after 15 it is removed at once. The top is 7, the largest of the three smallest, which is the 3rd smallest overall.

Exercise 3. Show the answer: a min-heap of size k keeps the k largest values, and its smallest value is the first to be removed when a bigger one arrives. The top is then the kth largest. A max-heap would hold the largest values with the biggest at the top, and you could not discard the weakest winner.

Exercise 4. Show the answer: store (-score, id) tuples. The negative score makes the higher score come first, and the id breaks ties in ascending order. For example, heapq.heappush(heap, (-score, id)).

Exercise 5. Show the answer:

import heapq
 
words = ["pear", "apple", "fig"]
heapq.heapify(words)
while words:
    print(heapq.heappop(words))

The strings are compared in their natural order, which is alphabetical for lowercase words. Popping always takes the smallest remaining word, so the output is alphabetical.

Exercise 6. Show the answer:

import heapq
from collections import Counter
 
def top_k_frequent(values, k):
    counts = Counter(values)
    return [v for v, _ in heapq.nlargest(k, counts.items(), key=lambda item: item[1])]

A version that uses a heap of size k directly keeps a min-heap of (count, value) pairs and pops whenever the heap grows past k.

Exercise 7. Show the answer: put the values in a set, then walk the numbers 1 to 10 and return the first one that is not in the set. For this task a set is simpler, because a set answers "is it there?" in O(1) on average, and the heap adds no value. The heap would matter only if the values kept arriving and you needed the smallest missing number at every moment.

Exercise 8. Show the answer: heappop removes the root and then moves the last item to the root. That item sinks down one level at a time, swapping with its smaller child. The tree has about log2(n) levels, so the item moves at most that many times. Each step does a fixed amount of work, so the total is O(log n). The rest of the heap does not need to move.

Exercise 9. Show the answer:

import heapq
 
def merge_two(a, b):
    lists = [a, b]
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        value, li, pos = heapq.heappop(heap)
        out.append(value)
        if pos + 1 < len(lists[li]):
            heapq.heappush(heap, (lists[li][pos + 1], li, pos + 1))
    return out

Two sorted lists can be merged with two indexes, without a heap, in O(n). The heap version is correct, but it adds overhead for only two lists. It becomes worth it when there are many lists, because the heap keeps the cost at O(log k) per item instead of scanning every list.

Exercise 10. Show the answer:

import heapq
from itertools import count
 
tie = count()
queue = []
for due, name in [(2, "report"), (1, "deploy"), (2, "email")]:
    heapq.heappush(queue, (due, next(tie), name))
while queue:
    due, _, name = heapq.heappop(queue)
    print(due, name)

The output is 1 deploy, then 2 report, then 2 email. Without the counter, two tasks with the same due time would be compared by name, which may not match arrival order, and a task with a payload that cannot be compared would raise TypeError. The counter keeps the earlier task first and never reaches a payload comparison.

What you now know

• heapq gives a min-heap on a plain list. The smallest value is always at index 0.
• heappush and heappop cost O(log n). Reading heap[0] costs O(1). Searching for an arbitrary value costs O(n).
• A heap is stored in a list. The parent of index i is at (i - 1) // 2, and its children are at 2 * i + 1 and 2 * i + 2.
• For a max-heap, store negated numbers. For your own order, use tuples or a dataclass with order=True.
• For the k largest values, use a min-heap of size k, or call heapq.nlargest.
• The running median uses two heaps, a max-heap for the lower half and a min-heap for the upper half.
• A counter in the tuple breaks ties in arrival order and keeps the heap from comparing payloads.