heapq, heapify and heap sort in Python

Why it matters

In lesson 1 you wrote a heap by hand. That is a good exercise, because it shows the mechanics. In real work, you rarely write your own heap. Python gives you the heapq module, a ready-made heap that works on a plain list. Interviewers expect you to use it fluently: to pick the right order, to break ties, to build it from a list, and to know what each operation costs. They also expect you to know the two results that make heaps special. The first is that a heap can be built from a list in linear time. The second is that a heap can sort a list in place, in O(n log n) time.

This lesson covers all of that. You will use heapq with a custom order, learn how tuples give you a tie rule, see why building a heap is faster than adding items one by one, and write a heap sort. Along the way you will meet the mistakes that cost points in interviews, and the exact messages Python prints when you make them.

The heapq module

heapq is a module, which means a file of ready-made functions. You import it with import heapq. It is a min-heap only. The smallest item comes out first. It stores its items in a normal Python list, just as lesson 1 did, and it keeps the heap property after every change.

Unlike lesson 1's class, heapq has no object. You keep the list yourself, and you pass it to each function. The list is the heap.

Here are the functions you will use most, with their costs. The costs assume n items are stored.

Two points in that table are often missed. First, heappop raises an error on an empty heap. It does not return None. Choose the way your code handles an empty heap before you write the loop, usually with while h:. Second, h.remove(x) breaks the heap. Removing an item from the middle of the list can leave a parent bigger than a child. If you must remove a specific item, call heapq.heapify(h) again afterwards. Usually the better design is to add a new entry and skip the old one when you see it later. Lesson 4 uses that idea.

There is one more trap, and it is a big one. Printing the list, or looping over it with for, does not give sorted order. The loop walks the list in index order. The heap only guarantees that the parent is smaller than its children, so the printed order looks random. Only repeated heappop calls return items in sorted order. The first runnable block shows this clearly.

Runnable example: min and max heaps

The next block builds two heaps from the same three numbers. The first is a min-heap, the default. The second is a max-heap. heapq has no option for a max-heap, so the trick is to store the negative of each number. The smallest negative is the biggest number. The section after this one explains the idea of an order in plain words.

The output is:

min heap internal: [1, 5, 4]
max heap internal: [5, 1, 4]
min pops: 1 4 5
max pops: 5 4 1

Trace the min heap. Push 5: the list is [5]. Push 1: it goes to index 1, its parent 5 is bigger, so it swaps to the top: [1, 5]. Push 4: it goes to index 2, its parent at index 0 is 1, which is smaller, so it stays: [1, 5, 4]. That is the first line of output. The printed list is a valid heap but not sorted, because 5 comes before 4.

Trace the max heap with the negatives. Push -5: [-5]. Push -1: it goes to index 1, its parent -5 is smaller, which is correct for a min-heap of negatives, so no swap: [-5, -1]. Push -4: index 2, parent -5 is smaller, so no swap: [-5, -1, -4]. The line prints the list with the signs flipped back, which gives [5, 1, 4].

The pops show the ordering promise. The min heap gives 1, 4, 5. The max heap gives 5, 4, 1.

Notice also that the heappop calls are inside one print. Each call removes one item, so the three calls give three different values. That is a common surprise for beginners who expect the same value to repeat.

Ordering in plain words

A heap decides order with one question: is item a smaller than item b? In Python, the answer comes from the < operator. The heap only ever asks a < b. If you want a different order, you change what gets compared.

There are three common ways to do that in Python.

The first is to change the number, as the max heap did. Negating a number reverses the order. This works for numbers only.

The second is to use a tuple. A tuple is a fixed group of values in parentheses, such as (2, "email"). Python compares two tuples one item at a time, from left to right. It moves to the next item only when the current items are equal. So (-5, 1) comes before (-2, 0), because -5 is smaller than -2. A tuple lets you write the whole rule in one line: first the main key, then the tie breaker. This is the form most Python programmers use with heapq.

The third is a class with an order. A dataclass with order=True compares its fields in the order they are written, just like a tuple. The example in the tie section shows it.

A comparator is a small function that says which of two items comes first. Python does not need one for heapq, because the tuple already is the rule. When you do have an old-style comparison function, functools.cmp_to_key turns it into a key that Python can use.

In languages with fixed-size integers, a subtraction such as a - b can overflow, which gives the wrong sign for big numbers. Python integers have no fixed size, so the subtraction is always exact:

The output is:

a - b = -4000000000
a - b is negative: True

Python integers grow as large as they need to be. You can still write a comparison with a tuple, which is clearer, but you do not need to worry about overflow.

Runnable example: break ties with tuples

Real queues often hold tasks, and tasks often have a priority and a second rule for ties. Here is a task queue. Each task has a name and a priority. A higher priority runs first. When two tasks have the same priority, the one that arrived first runs first. To keep arrival order, the program stores the arrival position with each task.

The tuple has three parts: the negative priority, the arrival position and the name. The negative priority makes the biggest priority come first. The arrival position breaks ties, with the smaller position winning. The name is only carried along and is never needed for ordering, because no two tasks share an arrival position.

The output is:

backup (priority 5)
alert (priority 5)
email (priority 2)
log (priority 1)

Look at the loop. enumerate(tasks) gives each task its position, 0, 1, 2 and 3. The tuple (-priority, arrival, name) is what the heap compares. Two tasks have priority 5. The backup task arrived at position 1 and the alert task at position 2. So backup leaves first. That is the tie rule working. Without the second item in the tuple, the order between them would depend on the internal list positions, and it would not be predictable.

The lesson to take from this: whenever the problem gives a tie rule, put it in the key. Never trust the heap to keep ties in the order they came in. A heap does not promise that.

The same rule can be written with a class. Here is the same queue with a dataclass. The field sort_priority comes first, so it decides the order. The compare=False setting on the other fields means they are carried along but never compared.

The output is:

Task(sort_priority=-5, arrival=1, name='backup', priority=5)
backup (priority 5)
alert (priority 5)
email (priority 2)
log (priority 1)
True

The first line is the smallest task in the heap, which is the one that will leave first. The last line shows the comparison directly: -5 is smaller than -2, so the first task is smaller.

Building a heap from a list in O(n)

Suppose you already have n items in a list and want a heap of them. You could call heappush once per item. Each push costs O(log n), so the total is O(n log n). That is fine for small inputs, but there is a faster way.

The faster way is called heapify. Put all the items in a list first, in any order. Then sift down every node that has at least one child. Start at the last such node and move back toward the root. The last node with a child is at index n // 2 - 1 (floor division). Each step fixes the sub-heap below one node, so when you finish at index 0, the whole list is a heap.

Why is that faster? Most nodes are near the bottom of the tree, and a node near the bottom has very little room to sift. Half of all nodes are leaves and do no work at all. A quarter of the nodes have only one level below them. Only a few nodes near the top can sift down a long way. When you add up all that work, the total is proportional to n, not n log n.

Here is a count for seven items, which fill three levels. The four leaves at the bottom need no work. The two nodes one level up can each sift down at most one level, so they cost at most two steps in total. The root can sift down at most two levels, which is two more steps. The total is at most four steps. Adding the same seven items one at a time can take up to 10 sift-up steps in the worst case. The gap grows with n.

The heapq module has this as a function, heapq.heapify. It changes the list in place and returns None:

The output is:

from list: [3, 5, 8]
from list: [1, 4, 2, 9, 8, 7, 6]

The list [5, 3, 8] was not a heap. Heapify started at index 3 // 2 - 1, which is 0, and sifted the root down. The 5 swapped with the 3, and the list became [3, 5, 8].

The second list shows that heapify does not sort. The result [1, 4, 2, 9, 8, 7, 6] has the heap rule, and its order is otherwise arbitrary.

Runnable example: watch heapify work

The next block heapifies a short list and prints every sift. Read it slowly. It shows exactly the loop from the theory above: start at n // 2 - 1, move back to 0, and sift down at each index. It uses a max-heap, because the same idea works for both kinds of heap, and the next section uses a max-heap for heap sort. A max-heap needs no negation here, because the function compares with >.

The output is:

start: [3, 9, 2, 1]
sift down from index 1 (value 9)
  now: [3, 9, 2, 1]
sift down from index 0 (value 3)
  now: [9, 3, 2, 1]
max-heap: [9, 3, 2, 1]

Here n is 4, so the loop starts at 4 // 2 - 1 = 1. Index 1 holds 9. Its only child is index 3, which holds 1. Since 9 is bigger than 1, nothing moves. Next is index 0, which holds 3. Its children are 9 at index 1 and 2 at index 2. The largest is 9, so 3 and 9 swap. The list is [9, 3, 2, 1]. Then 3 sits at index 1, and its child at index 3 holds 1. Since 3 is bigger, the sift stops.

Only one swap happened in the whole build. That is why heapify is cheap on this list. A note to take away: the printed line "sift down from index 1" does not mean index 1 moved. It only means the code looked at it.

The function returns the number of swaps it made. This block ignores that number. The next block uses it.

Heap sort

A heap can sort a list in place, meaning it reuses the list and needs no second list of the same size. The method is called heap sort, and it has three steps.

Step one: heapify the whole list into a max-heap, so the largest value is at index 0.

Step two: swap the value at index 0 with the value at the last position of the heap. The largest value is now in its final sorted place, at the end.

Step three: shrink the heap by one, so the last position is no longer part of it. Sift down the new value at index 0. The heap is valid again for the smaller size. Go back to step two until the heap has only one value.

Think of a line of cards on a table. You keep the biggest card at the front of a pile. You move it to the end of the sorted row. Then you fix the pile, and repeat. Each round places one more card in its final spot.

The sorted list fills from the right. The first swap places the biggest value at the last index. The second places the second biggest just before it, and so on. When the heap is empty, the list is sorted in ascending order.

Heap sort costs O(n log n) in every case. The heapify step costs O(n). Then there are n rounds, and each round sifts down once, which costs O(log n). The best case, the worst case and the average case are the same, unlike quicksort, which can slow down on bad inputs. Heap sort also uses only a few extra variables, so its extra space is O(1). It is not a stable sort: two equal values can change their relative order. That matters when you sort records by one key and need the old order kept for ties. Python's built-in sorted() and list.sort() are stable, so they keep the old order for ties.

The visualizer below shows selection sort. Heap sort is a cleverer version of the same idea: selection sort searches the whole unsorted part for the biggest value each round, which costs O(n) per round, while heap sort finds it in O(1) and repairs the heap in O(log n). Watch how the sorted part grows at the end of the list.

Runnable example: heap sort with a swap counter

The next block sorts two lists with heap sort and counts every swap. The function heap_sort changes the list it is given, and it returns the swap count.

The output is:

1 2 4 6 7 8 9
swaps: 11
1 3 4 5 10
swaps: 9

The swap count includes swaps made during heapify and swaps made during the sorting rounds. The count is the sum of the returned numbers, and each swap adds one.

Notice copy = list(data). It makes a new list with the same values. Without it, heap_sort would change the original list, data. In Python, passing a list to a function gives the function the same list, not a copy. Changes made inside the function are visible outside it.

The sorting itself is what matters. The first list was 9 4 7 1 8 2 6, and the output is the same numbers in ascending order. The count of 11 depends on the input. A different input of the same size can give a different count, and that is normal.

Now trace the second, smaller input by hand. The list is 4 10 3 5 1. Heapify makes two swaps: at index 0 the 10 rises, then at index 1 the 5 rises, giving 10 5 3 4 1. Round one swaps the 10 to the end, leaving 1 5 3 4 10, then sifts the 1 down. It makes three swaps in all, in round one. Round two swaps 5 to the end and sifts the 1 down once, for two swaps in all. Round three uses one swap and round four uses one swap. Add up the swaps: heapify made two, and the rounds made three, two, one and one. Two plus seven makes nine.

Heap sort in practice and in interviews

A heap sort is rarely the fastest choice in practice. Quicksort and merge sort are usually faster on real data because they use the processor cache well. Python's built-in sort is a merge-based method called Timsort. It is stable, and it is what you should use in real code. Heap sort is still worth knowing for three reasons. It guarantees O(n log n) with no bad inputs. It uses almost no extra memory. And it teaches the same sift operation that the heap data structure needs.

Interviewers ask heap sort questions to see whether you understand the sift operation. A common question is "why does heap sort need a max-heap to sort in ascending order?" The answer is that the max-heap puts the largest value at index 0, and the swap to the end places that largest value in its final spot. A min-heap would put the smallest at the top, and swapping it to the end would build the list in descending order.

Worked example: Dijkstra's shortest path, step by step

Dijkstra's algorithm finds the shortest distance from one start node to every other node in a weighted graph. A weight is the cost of one edge, and the algorithm needs every weight to be zero or more. The heap holds pairs of (distance, node) that are waiting to be processed, and it always gives the pair with the smallest distance. The tuple puts the distance first, so the heap compares distances. The program below is this algorithm on a graph with five nodes. Its output lists the order in which the nodes are finished. It needs no input, so the Run button starts it directly.

The output is:

visit 0 at distance 0
visit 2 at distance 1
visit 1 at distance 3
visit 3 at distance 4
visit 4 at distance 7
shortest: [0, 3, 1, 4, 7]

The graph has these edges, and each edge works in both directions: node 0 to node 1 costs 4, node 0 to node 2 costs 1, node 2 to node 1 costs 2, node 1 to node 3 costs 1, node 2 to node 3 costs 5, and node 3 to node 4 costs 3.

Step 1. The heap holds (0, 0), the start node at distance 0. Pop it and print visit 0 at distance 0. Look at its neighbours. Node 1 is reachable at 0 + 4 = 4, and node 2 at 0 + 1 = 1. Both beat the starting value of infinity, so both are stored in dist, and both pairs go into the heap.

Step 2. The smallest pair is (1, 2). Pop it and print visit 2 at distance 1. Its neighbours are node 0, which would be at distance 2 and does not help, node 1, which would be at 1 + 2 = 3 and beats 4, and node 3, which would be at 1 + 5 = 6. Update the distances of nodes 1 and 3, and push (3, 1) and (6, 3).

Step 3. The smallest pair is now (3, 1). Print visit 1 at distance 3. Node 3 can be reached at 3 + 1 = 4, which beats 6, so push (4, 3). The heap still holds two old pairs: (4, 1), an older and worse distance to node 1, and (6, 3), an older and worse distance to node 3.

Step 4. The smallest pair is (4, 1), an old entry. Its distance 4 is bigger than the best known distance to node 1, which is 3, so the line if d > dist[u]: continue skips it. The next smallest is (4, 3). Print visit 3 at distance 4. Node 4 can be reached at 4 + 3 = 7, so push (7, 4).

Step 5. The heap holds (6, 3) and (7, 4). Pop (6, 3), which is skipped for the same reason, because 6 is bigger than the best known distance to node 3, which is 4. Pop (7, 4) and print visit 4 at distance 7. The heap is empty, and the program prints shortest: [0, 3, 1, 4, 7].

The old pairs are the important part. A node can be pushed several times, once for each better distance that is found. Only the pair that carries the current best distance should be expanded. The check skips the rest. Without the check, the answer is still correct, but the program expands old pairs and does extra work. Each skipped pair still costs one pop, which is O(log n), so the check saves real time on a large graph. This habit of leaving old entries in the heap and skipping them later is called lazy deletion, and lesson 4 uses the same idea.

The heap is what makes this fast. Without it, each step would scan every unfinished node to find the closest one, which costs O(n) per step and O(n²) in total. With the heap, each push and each pop costs O(log n), and the total is O(E log V), where E is the number of edges and V is the number of nodes.

How heap sort compares with other sorts

Heap sort is one of several sorts that take O(n log n) time in the usual case. The table below compares the three you will be asked about most often.

Heap sort's strength is its guaranteed worst case, with almost no extra memory. Quicksort is usually faster in practice, because its partitioning walks the list in order and uses the processor cache well. Its weakness is the rare bad input that makes it O(n²), although good pivot choices make that very unlikely. Merge sort is stable and predictable, but it needs a second list of the same size.

When an interviewer asks which sort to use on a small memory budget with a guaranteed time limit, heap sort is a strong answer, because it meets both limits. When the data is large and speed matters most, the usual answer is quicksort or merge sort, and the reason is the cache and the memory traffic, not the big-O bound. In your own Python code, call sorted(), which is stable and fast.

An interview conversation

A common interview prompt is this: "You have jobs, each with a priority. Higher priority runs first. If two jobs have the same priority, the job that arrived first runs first. Design the queue."

A strong answer goes in order. First, name the structure: a heap, using heapq, because the job with the best rule must come out first. Second, describe the key in one sentence: compare priority, bigger first, and if they are equal, compare the arrival number, smaller first. Third, say how arrival is stored: itertools.count() gives 0, 1, 2 and so on, one number for each job, so the tie rule is deterministic. Fourth, state the costs: each push and each pop costs O(log n), and reading the next job with queue[0] costs O(1). Fifth, mention the edge case: heappop raises IndexError on an empty heap, so the caller must check if queue: before popping.

The interviewer usually then asks what happens if a job's priority changes while it waits. A good answer is to add a new entry with the new priority and mark the old one as dead, then skip dead entries when they come out. That is lazy deletion again, and it avoids the O(n) search of remove.

Common mistakes and the messages they produce

Mistake 1: printing the heap list and expecting sorted output. The printed order is the list order, which only promises parent-child order. Use repeated heappop calls to read items in order.

Mistake 2: putting items in a heap that cannot be compared. A heap compares items with <. Mixing types fails with this message:

TypeError: '<' not supported between instances of 'str' and 'int'

The same kind of error appears when a tuple's first items are equal and the second items cannot be compared. Here the second items are two different dictionaries:

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

The fix is to give every item a key that Python can compare, such as a number, or a number followed by an arrival position.

Mistake 3: popping an empty heap and expecting None. heappop raises an error on an empty list. The message is short:

IndexError: index out of range

Check if queue: or while queue: before you pop. Reading queue[0] on an empty list raises a different message, IndexError: list index out of range.

Mistake 4: using / for the heapify start. In Python, / gives a float, and a list cannot be indexed with a float. Writing n / 2 - 1 gives this error:

TypeError: list indices must be integers or slices, not float

The fix is n // 2 - 1.

Mistake 5: heapifying from index 0 upward. Starting at index 0 and going up does not fix the sub-heaps below. Heapify must start at n // 2 - 1 and go down to 0. Starting at 0 gives the wrong result, because the children of the root may not yet be heaps when the root is sifted. Note that heapq.heapify already does this for you.

Mistake 6: forgetting to negate for a max heap. heapq always gives the smallest item first. If you push the positive numbers and pop them, you get the smallest first. For the largest first, push the negatives and negate each popped value.

Mistake 7: removing an item from the middle of the list. h.remove(x) searches the list, which costs O(n). It also can break the heap rule, so the list may need heapq.heapify(h) again. In a loop, that search costs O(n²) in total. Prefer lazy deletion, which lesson 4 shows. If an item is missing, remove raises this message:

ValueError: list.remove(x): x not in list

Debugging walkthrough

Suppose your heap sort returns the wrong order on one input. Start by printing the list after heapify. Check the parent-child pairs using the method from lesson 1. If the list after heapify is not a max-heap, the bug is in heapify or sift down. Look at the starting index first. A common mistake is i = n // 2 - 2, which skips the last node that has children. A different mistake is i >= 1 instead of i >= 0, which skips the root.

If the list after heapify is a max-heap but the final output is wrong, the bug is in the sorting rounds. Print the list after each swap and after each sift. Look at the range the sift uses. It must be end, the size of the shrinking heap, not n. If the sift uses n, it pulls sorted values back into the heap and the result is broken.

If the program works for many inputs but fails for one, check the edges. An empty list has n = 0, so the loop from n // 2 - 1 starts at -1 and does nothing. The sorting loop runs from end = n - 1 = -1, so it also does nothing. That is correct. A list of one value does no work at all. Test both before you submit.

Variations and edge cases

A descending heap sort is the same idea with the comparisons flipped. A min-heap sort puts the smallest value at the end first, so the list comes out in descending order when read from index 0. Many people find that confusing, so state the direction in your answer.

Sorting objects uses the same code with a key. The tasks in the tie example can be sorted by priority by comparing the tuple or the dataclass, instead of comparing plain numbers.

Duplicates are handled correctly. Two equal values simply sit near each other in the result. Heap sort is not stable, so do not rely on the original order of equal items.

Very large lists are sorted in O(n log n) time and O(1) extra space. The time is fine, but the memory access pattern is not cache-friendly. Real libraries prefer other sorts for large data.

Top k items is a common heap task. heapq.nlargest(k, items) returns the k biggest items, and heapq.nsmallest(k, items) returns the k smallest. You do not need to sort the whole list first. For example, heapq.nlargest(2, [5, 1, 9, 7]) returns [9, 7].

Interview patterns from this lesson

Three patterns come up again and again. Write them down, because the next lessons use them.

The first pattern is a heap with a custom key. Whenever the problem says "process the most urgent item first" or "the item with the biggest score", use heapq with a tuple that encodes the rule. Put every tie rule inside the tuple.

The second pattern is heapify for a whole list. When you already have the data, do not push items one at a time. Call heapq.heapify on the list, to get O(n) instead of O(n log n).

The third pattern is heap sort as a fallback. It guarantees O(n log n) and uses constant extra space, so it is a safe answer when an interviewer asks for a sort with a worst-case guarantee and little memory.

Complexity summary

Practice

Exercise 1. Write a key for strings that puts longer strings first. For strings of equal length, put the alphabetically smaller one first. Use it with heapq on the list ["pear", "fig", "banana", "apple", "kiwi"]. Hint: the key is a tuple of the negative length and the string itself.

Show the answer

The key is (-len(s), s). Push each string as (-len(s), s) and pop them all. The result is ['banana', 'apple', 'kiwi', 'pear', 'fig']. The first part of the tuple puts the longest first. Longer strings have a more negative first item, so they are smaller. The second part breaks ties alphabetically, because "kiwi" comes before "pear".

Exercise 2. Trace heapq.heapify on [3, 9, 2, 1], but as a max-heap, as the runnable block does. Write the list after each sift. Hint: start at index 1.

Show the answer

Start: [3, 9, 2, 1]. Sift from index 1: its child at index 3 holds 1, which is smaller than 9, so nothing moves. Sift from index 0: the children are 9 and 2, the largest is 9, so swap to [9, 3, 2, 1]. At index 1, the child 1 is smaller than 3, so the sift stops. Final: [9, 3, 2, 1].

Exercise 3. Explain in your own words why heap sort needs a max-heap to produce an ascending list in place.

Show the answer

The largest value sits at index 0 in a max-heap. Swapping it with the last heap position puts it in its final ascending spot, and the heap shrinks by one. A min-heap would place the smallest value at the end, which builds the list in descending order.

Exercise 4. What does heapq.heapify([5, 3, 8]) leave in the list? Explain why it is not [5, 3, 8].

Show the answer

It leaves [3, 5, 8]. The list [5, 3, 8] breaks the heap rule at the root, because 5 is bigger than its child 3. Heapify sifts 5 down, and 3 moves up to the top.

Exercise 5. Write a key for pairs (id, cost), where the lowest cost comes first and the lower id breaks ties. Avoid subtraction. Test it with the pairs (3, 1), (1, 9), (2, 1) and (5, 0), written as (id, cost).

Show the answer

Store each pair as (cost, id). Python compares the cost first and the id second, so no separate comparison function is needed. The pairs come out as (0, 5), (1, 2), (1, 3), (9, 1), which means ids 5, 2, 3, 1. The two pairs with cost 1 come out in id order, 2 before 3.