Debugging lab: heap bugs in Python

Why this matters

A heap bug is hard to see. The program runs, it prints numbers, and most of the numbers look reasonable. The wrong answer only appears when you compare the output with the correct order, and often only in a few cases. Heaps sit inside schedulers and job queues, so a heap bug can show up as the wrong job running first in a larger system.

This lab gives you four broken heaps. Each one has a different kind of bug. For each bug you will see the symptom, read the code, find the cause and fix it. The fixes are checked against sorted output, so you can see that the heap is right, not only that it looks right.

The lab uses the array-based heap from the earlier lessons of this module. Its two methods are add, which puts a value in, and poll, which removes and returns the smallest value. In Python the array is a list. You should know that the parent of index i is at (i - 1) // 2, and that the children of index i are at 2 * i + 1 and 2 * i + 2. The // operator is integer division: it divides and drops the fraction. The labs depend on those two formulas.

A method for finding heap bugs

Before the four labs, here is the method you will use in each one. Engineers use the same steps on real code.

1. Start with a small input. Use 5 to 7 numbers. Small inputs are easy to trace by hand.
2. Write the expected answer. For a min-heap, the expected output of repeated poll calls is the input sorted from smallest to largest. Write it down before you run the code.
3. Print the list after each step. The list is the heap. If you print only the final answer, you cannot see where it went wrong.
4. Write a checker. A checker is a small function that tests the heap rule. For a min-heap, the rule is: every parent is less than or equal to its children. The checker below does this for a list.
5. Find the first step that goes wrong. Once the output is wrong, look back for the first list state that breaks the rule. The bug is in the code that made that change.

Here is the checker, used in all four labs:

def is_min_heap(a, size):
    for i in range(1, size):
        if a[(i - 1) // 2] > a[i]:
            return False
    return True

The loop starts at index 1, because index 0 has no parent. For each index, it looks up the parent with (i - 1) // 2 and compares. If any parent is larger than its child, the heap is broken, and the function returns False.

Only the first size slots are checked. The list can have unused slots after them, and the checker skips those.

Lab 1: a reversed comparison

Here is a small heap class with a method called before. The method says whether one value should be closer to the top than another. The heap uses before for both moving a new value up and moving the root value down.

The class keeps its values in self.a, a list with 16 slots. [None] * 16 makes a list of 16 empty slots. The field size says how many slots are in use. The slots after size are not part of the heap.

The test adds 5, 1, 9 and 3, and then calls poll until the heap is empty. Output:

array: [9, 3, 5, 1]
polls: 9 5 3 1

The expected output for a min-heap is 1 3 5 9. The output is the reverse. The list [9, 3, 5, 1] already shows the problem: 9 is at the top, and every child is smaller than its parent. The heap is a max-heap, where the largest value is at the top.

Finding the cause

Read before first. It returns x > y. A min-heap needs before to mean "x is smaller than y", which is x < y. Both add and poll use before, so one wrong line reverses the whole heap. Read the if in add again: not self.before(self.a[i], self.a[p]) means "stop when the child is not before the parent". With the reversed rule, a larger child moves up.

A reversed comparison is an easy bug to make, for example when a max-heap example is copied and the comparison is not flipped.

Fix

Change one line:

return x < y

Run the same test again with the fixed before, and the output becomes the sorted list. The fixed version is in the final section, where the labs are fixed and checked together.

Lab 2: an off-by-one child index

This heap has a bug in poll. The add method is correct. Make a copy of the Lab 1 class named HeapOffByOne, change before to return x < y, and put this poll in place of the Lab 1 one. Here is poll with the bug:

    def poll(self):
        top = self.a[0]
        self.size -= 1
        self.a[0] = self.a[self.size]
        i = 0
        while True:
            l = 2 * i  # bug: left child should be 2 * i + 1
            r = 2 * i + 2
            best = i
            if l < self.size and self.before(self.a[l], self.a[best]):
                best = l
            if r < self.size and self.before(self.a[r], self.a[best]):
                best = r
            if best == i:
                break
            self.swap(i, best)
            i = best
        return top

The bug is in the line that sets l. It should be 2 * i + 1, but it is 2 * i. The right child uses 2 * i + 2, so writing 2 * i for the left child is an easy slip. An off-by-one error is a mistake of one position, and it is common in index arithmetic.

Run the test with 7 numbers:

h = HeapOffByOne()
for x in [5, 1, 9, 3, 7, 2, 8]:
    h.add(x)
print("array before polls:", h.a[:h.size])
print("is_min_heap:", is_min_heap(h.a, h.size))
polls = []
while h.size > 0:
    polls.append(h.poll())
print("polls:", *polls)

Output:

array before polls: [1, 3, 2, 5, 7, 9, 8]
is_min_heap: True
polls: 1 2 7 8 5 9 3

The checker returns True before any poll. So add builds a valid heap, and the bug is only in poll. This is an important lesson for debugging. The first thing you check should be whether the heap is valid after each operation, not only at the end.

The polls are 1 2 7 8 5 9 3. The sorted list is 1 2 3 5 7 8 9. The first two values are right, and the third is wrong. Print the list after each poll to find the exact step:

poll 1 -> left in heap [2, 3, 7, 5, 8, 9]
poll 2 -> left in heap [7, 3, 8, 5, 9]
poll 7 -> left in heap [8, 3, 9, 5]
poll 8 -> left in heap [5, 3, 9]
poll 5 -> left in heap [9, 3]
poll 9 -> left in heap [3]
poll 3 -> left in heap []

The list [7, 3, 8, 5, 9] is the state after the second poll. The root is 7, and its child at index 1 is 3. is_min_heap would return False at this point, because the parent (7) is larger than the child (3). The break happened during the second poll.

Walking through the second poll

Start with the list [2, 3, 7, 5, 8, 9]. The second poll takes the top value 2 and moves the last value 9 to the root. The list is now [9, 3, 7, 5, 8], with size 5.

The loop in poll that moves the root down starts at index 0 with i = 0. The buggy code computes l = 2 * 0 = 0. Index 0 is the node itself, so the comparison of self.a[0] with itself is false and nothing happens on the left side. The real left child, index 1 (value 3), is never looked at. The right child at index 2 (value 7) is smaller than 9, so 9 and 7 swap, giving [7, 3, 9, 5, 8]. The loop moves to index 2. The buggy left formula gives 2 * 2 = 4, which holds 8, so 9 and 8 swap, giving [7, 3, 8, 5, 9].

The value 3 at index 1 is now a child of 7, and 3 is smaller than 7. The loop never compared them, so the heap rule is broken, and nothing repairs it. The next poll returns 7 instead of 3.

This shows why a wrong child index is hard to find from the output alone. The program keeps running, and the broken rule shows only when a value comes out too early.

Fix

Change the formula for the left child:

l = 2 * i + 1

With this change, the same 7 numbers come out in sorted order, as the final section shows.

Lab 3: a key that changes while it is in the heap

This heap uses the standard library module heapq. The module keeps a plain list, with the smallest item at index 0. It compares items with the < operator, so the items need a way to answer that question. The Task class below defines __lt__, the method Python calls for <, so that two tasks are compared by their priority. Its priority is a number that can be changed. The __repr__ method controls how a task is printed.

Output:

peek after mutating a: b(3)
polls: b(3) a(1) c(8)

The task a has priority 1 at the end, which is the smallest of the three. The correct first result is a(1). The heap returns b(3) first, because heappush placed a at the top when its priority was 5. Then b came in with priority 3, which is smaller, so b moved to the top and a moved under it. After that, the priority of a changed to 1, and the heap did not know about it.

The bug is silent. No exception is raised, and the output is a plausible list of tasks. Only a comparison with the expected order shows the problem.

Finding the cause

When the three heappush calls ran, the heap stored the tasks in an order based on priorities 5, 3 and 8. Then a.priority = 1 changed the value in place, and a sits below b in the list. The heap rule (parent smaller than child) is now broken, but heapq does not check it when a field changes. It only compares items during heappush and heappop.

The rule is simple to state: the key of an item in a heap must not change while the item is in the heap. A class whose comparison reads a field is safe only if no code changes that field while the item is in the heap.

Fix: remove, change, add back

When you need to change a key, take the item out, fix the heap, change the key, and push the item back. heapq has no remove method, so the removal uses the list method list.remove. That method looks for the first item that compares equal with ==. The Task class has no __eq__ method, so Python uses object identity here: two names are equal only when they point to the same object. That means remove finds exactly the task you passed in.

Removing from the middle of a list can break the heap rule, so the code calls heapq.heapify to rebuild the rule on the list.

heap2 = []
a2 = Task(5, "a")
b2 = Task(3, "b")
c2 = Task(8, "c")
heapq.heappush(heap2, a2)
heapq.heappush(heap2, b2)
heapq.heappush(heap2, c2)
heap2.remove(a2)
heapq.heapify(heap2)
a2.priority = 1
heapq.heappush(heap2, a2)
print("peek:", heap2[0])
polls = []
while heap2:
    polls.append(heapq.heappop(heap2))
print("polls:", *polls)

Output:

peek: a(1)
polls: a(1) b(3) c(8)

The order is now correct. The cost is a search: list.remove looks through the list one item at a time, and heapq.heapify checks the whole list again. Both take time that grows with the heap size. For a heap that changes its keys often, the indexed heap from lesson 12 of this module is the better choice, because it knows where each item is.

If the class compares by value, remove can take out the wrong item. A @dataclass (a class that Python builds with a == that compares its fields) does this by default:

from dataclasses import dataclass
 
 
@dataclass
class Job:
    priority: int
    name: str
 
 
x = Job(3, "x")
y = Job(3, "x")
print("x == y:", x == y, "x is y:", x is y)
items = [x, y]
items.remove(y)
print("left in list is y:", items[0] is y)

Output:

x == y: True x is y: False
left in list is y: True

The two objects have the same fields, so x == y is True, even though they are two different objects. items.remove(y) took out x, the first item that compared equal. Keep identity comparison for items that you remove later, or give each item a unique id field and compare by that field.

If you know Java, heapq does the job of PriorityQueue, but it has no remove method.

Lab 4: running past the end of the list

A Python list grows when you call append, so a list-based heap does not run out of room by itself. The error in this lab comes from a list that was made with a fixed number of slots and is then written by index. The Lab 1 class has room for 16 values. Adding a 17th value writes to index 16, which does not exist.

full = HeapReversed()
try:
    for x in range(17):
        full.add(x)
except IndexError as e:
    print("IndexError:", e)

Output:

IndexError: list assignment index out of range

The message says that the index in an assignment is out of range. The valid indexes are 0 to 15, and the list has 16 slots. The fix is to add slots when the list is full. The extend method adds as many empty slots as the list already has, so the length doubles:

class GrowingHeap:
    def __init__(self):
        self.a = [None] * 4
        self.size = 0
 
    def add(self, x):
        if self.size == len(self.a):
            self.a.extend([None] * len(self.a))
        self.a[self.size] = x
        i = self.size
        self.size += 1
        while i > 0:
            p = (i - 1) // 2
            if self.a[i] >= self.a[p]:
                break
            self.a[i], self.a[p] = self.a[p], self.a[i]
            i = p

append does this growth for you, and the exact growth amount is an internal detail of CPython, the standard Python implementation, so do not depend on it. The explicit version shows the idea that a fixed-size array needs.

Add the values 17, 16, ..., 1 (17 values in total) to this version:

g = GrowingHeap()
seen = [len(g.a)]
for x in range(17, 0, -1):
    g.add(x)
    if len(g.a) != seen[-1]:
        seen.append(len(g.a))
print("lengths seen:", seen)
print("length:", len(g.a))
print("size:", g.size)
print("is_min_heap:", is_min_heap(g.a, g.size))

Output:

lengths seen: [4, 8, 16, 32]
length: 32
size: 17
is_min_heap: True

The length went 4, 8, 16, 32. The growth happened on the fifth, ninth and seventeenth adds, and the heap passes the checker.

The fixed heap

Labs 1, 2 and 4 are fixed in one class, and Lab 3 is fixed with the remove, change and add back steps. The fixed class is a min-heap with the correct child formula, the correct comparison and room to grow. It is tested against the output of sorted (a built-in function that returns a new sorted list) on 1000 random inputs.

Output:

fixed polls: 1 2 3 5 7 8 9
random trials with wrong output: 0

The random test uses a fixed seed (7), so every run tests the same 1000 inputs. A fixed seed makes a failure easy to repeat. When you find a bug with random tests, print the input that failed, and then run it by hand.

The standard library's heapq module does the same job with heappush and heappop. The labs write the heap by hand so that you can see each step.

Common mistakes

Printing only the final output. A wrong final list tells you that something is wrong, but not where. Print the list after each add and poll, and check the heap rule at each step.

Fixing the symptom with a sort. Calling sorted or list.sort on the list before each poll hides the bug and makes the heap pointless. The purpose of the heap is to avoid sorting the whole list each time.

Checking the child formula in your head. Write it down with numbers. For index 0, the children are 1 and 2. For index 1, they are 3 and 4. If your formula gives 0 or 2 for the left child of index 0, it is wrong.

Using / instead of //. In Python, / always gives a float, so (2 - 1) / 2 is 0.5. A float cannot be a list index:

a = [5, 1, 9]
i = 2
print(a[(i - 1) / 2])

Output (the last line of the error report; the lines above it show the file and line number):

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

Reading index -1 by accident. In Python, (0 - 1) // 2 is -1, not 0 as it would be in some other languages. A negative index counts from the end of the list, so a[-1] gives the last item and raises no error:

a = [5, 1, 9]
print((0 - 1) // 2)
print(a[(0 - 1) // 2])

Output:

-1
9

This is why the add loop checks i > 0 before it computes a parent.

Changing a key and expecting the heap to update. The heap does not watch its items. The error does not appear until a wrong value comes out. Remove the item, fix the heap with heapq.heapify, change the key, and push the item again.

Missing the growth check. The error is IndexError: list assignment index out of range. Check self.size == len(self.a) before writing.

Expecting heapq to be a max-heap. heapq is a min-heap, so the smallest item comes out first. Pushing 3, 1 and 2 and calling heappop returns 1. For the largest item first, push the negative of each number and negate the result:

import heapq
 
h = []
for x in [3, 1, 2]:
    heapq.heappush(h, -x)
print(-heapq.heappop(h))

Output:

3

Practice

Exercise 1. A student computes the parent of index i as i // 2. Find every index from 1 to 4 where this gives the wrong parent, and say what the correct parent is.

Show the answer

The correct parent is (i - 1) // 2, which gives 0, 0, 1, 1 for indexes 1 to 4. The student's i // 2 gives 0, 1, 1, 2. Index 1 and index 3 are correct. Index 2 gives 1, but the correct parent is 0. Index 4 gives 2, but the correct parent is 1.

Exercise 2. Write a function check_sorted(values) that returns True if the list is in non-decreasing order (each value is greater than or equal to the one before it). Use it to test the output of the heap in Lab 2.

Show the answer

def check_sorted(values):
    for i in range(1, len(values)):
        if values[i] < values[i - 1]:
            return False
    return True

Applied to the Lab 2 output 1 2 7 8 5 9 3, this function returns False, because 5 comes after 8, and 3 comes after 9. The check is useful for a test that records the values from repeated poll calls into a list.

Exercise 3. A heapq heap holds a task with priority 9. Its priority is changed to 1 while it is in the heap. Write the steps to correct the heap order, and say why a plain heappush after the change is not enough.

Show the answer

Remove the task from the list while its priority is still 9. Call heapq.heapify on the list, so the heap rule holds again. Then change the priority to 1, and call heapq.heappush with the task. A plain push after the change is not enough, because the task is still in the list, in the place that priority 9 gave it. The list would then hold the same task twice, and the heap rule can still be broken at the old place.

Exercise 4. In the reversed heap from Lab 1, the comparison is return x > y. How many lines must change to turn it into a min-heap, and why?

Show the answer

One line: return x < y. Both add and poll call before, and both get the correct order from the single method. This is why it is good design to put the comparison in one place. A bug in one place is easier to find and to fix than the same comparison written in several places.

Exercise 5. A heap starts with a list of length 4 and grows with extend([None] * len(self.a)). After how many adds does the list grow for the first time, and what is its length after the first growth?

Show the answer

The list grows when size equals its length. With length 4, the fifth add finds size == 4 and grows the list. After the growth, the length is 8. The earlier four adds fit in the first list, so the first growth happens on the fifth add.

Summary

• A heap bug often shows only in the output, not in an error. Use a small input, the expected sorted output and a checker to find it.
• Print the list after each step. The first list that breaks the heap rule points to the bug.
• A reversed comparison makes a min-heap into a max-heap. Check the single comparison that both add and poll use.
• The left child of index i is 2 * i + 1. A missing + 1 looks like the right formula but gives the wrong child.
• Do not change a key while the item is in the heap. Remove it, fix the heap with heapq.heapify, change the key, and push it again.
• Check self.size == len(self.a) before writing a new value, and grow the list when it is full.