Debugging lab: heap bugs

Why this matters

Heap code is short, and most of it is index arithmetic. A parent sits at index (i - 1) / 2, and its children sit at 2 * i + 1 and 2 * i + 2. A single wrong number in these formulas, or a single comparison pointing the wrong way, gives a heap that looks fine on a small test and returns the wrong item on a larger one.

Interview problems and real code often need a heap that you write yourself, for example to support a special rule or to change a key in place. The standard library's std::priority_queue does not offer every operation, so a program may need its own heap. This lesson gives you a broken heap and a set of tests, and walks through finding each bug.

The rules of a heap and the comparator ideas are covered in the earlier lessons of this module, so this lesson does not explain them again. The lab uses a min heap. Its top item is the smallest value.

The method for a heap bug

A heap bug shows up in one of three ways: the program crashes, a checker says the heap rule is broken, or the output is in the wrong order. Each symptom has a matching tool.

1. A crash or an assertion message gives a file and a line. Read the message and the line before changing anything.
2. A checker function, called is_heap in this lesson, walks the array and tests every parent against its children. It returns false at the first broken pair. It works on any heap, and it points at the rule that failed.
3. A small test with a known answer, such as "pop all items and compare with a sorted copy", shows whether the public behaviour is right.

The steps below follow this order. Fix one bug, run the tests again, and then move to the next bug. Changing several things at once makes it hard to tell which change helped.

The lab program

The program below is a min heap stored in a std::vector<int>. It has three tests. It contains three bugs, and the lab asks you to find them. Do not read the fixes yet.

The three tests check different things. Test 1 checks the heap rule right after the pushes. Test 2 checks the public behaviour, which is that the pops come out sorted. Test 3 checks a key that was lowered in place, and the smallest item must now be the new value.

Step 1: read the crash

Save the program as lab.cpp, then compile and run it:

g++ -std=c++20 -Wall -o lab lab.cpp && ./lab

On the g++ 15 build used for this lesson, the program stops with this message:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The exit code is 134, which means the program was stopped by an abort signal. Two things stand out. The first line of the message is long, but the important part is Assertion '__n < this->size()' failed. That means some code asked the vector for an index that is not in the vector. The second thing is that the test 1 line is missing. The lines were written to cout, which holds output in a buffer until it is flushed. When the output goes to a file or a pipe, the abort stopped the program before that buffer was written out, so the line was lost. In a terminal, the test 1 line appears before the message.

The message does not name the line in lab.cpp that caused the bad index. The call that failed is pop, which calls sift_down (it moves an item down the heap until its children are no smaller), so the bad index comes from there. Look at the child bounds in sift_down.

size_t left = 2 * i + 1;
size_t right = 2 * i + 2;
if (left <= n && data_[left] < data_[smallest]) smallest = left;

The valid indexes of a vector with n items run from 0 to n - 1. The test left <= n lets left equal n, and data_[n] is one past the end. The correct test is left < n. This is an off-by-one error in the bound, which means the bound is one step too far.

Change the one line:

if (left < n && data_[left] < data_[smallest]) smallest = left;

Run the program again with this change.

test 1 is_heap after pushes: FAIL
test 2 pops in sorted order: FAIL
        popped: 9 2 3 1 5 8
test 3 smallest after lowering key: 7 (expected 1)

The crash is gone, and the tests now print. Test 1 fails, so the heap rule is already broken after the pushes. Test 2 gives an order that is not sorted.

Step 2: a checker that points at the rule

Test 1 says the heap rule fails right after the pushes. The is_heap function does not say which pair is wrong. Find the bad pair by hand, with a small input.

Push 5, then 3, then 1. Trace sift_up for each push. It moves a new item up while its parent is larger. The first push leaves [5]. The second push puts 3 at index 1, with parent index 0 holding 5. The line if (data_[parent] >= data_[i]) break; checks whether the parent is greater than or equal to the new item. Here 5 is greater than 3, so the test is true and the loop stops without swapping. The heap is now [5, 3], where a min heap needs [3, 5].

This program runs the same steps and prints the array:

Output:

5 3 1 

The root (index 0) holds 5, which is the largest item. A min heap must hold the smallest item at the root. The bug is in the comparison: the code swaps when the parent is smaller, and stops when the parent is larger. It should be the other way round. The correct stop test is that the parent is already smaller or equal, which is if (data_[parent] <= data_[i]) break;.

Apply this fix and run the program again.

test 1 is_heap after pushes: PASS
test 2 pops in sorted order: PASS
        popped: 1 2 3 5 8 9
test 3 smallest after lowering key: 4 (expected 1)

Tests 1 and 2 pass. Test 3 still fails, and this is the third bug.

Step 3: a key changed in place

Test 3 pushes 4, 7 and 6, which gives the heap [4, 7, 6]. The test then calls set(2, 1), which changes the item at index 2 from 6 to 1. The set function writes the value and returns. It does not move the item to its correct place. The array becomes [4, 7, 1], which breaks the heap rule because index 2 (value 1) is smaller than its parent at index 0 (value 4). The pop then returns the root, which is 4.

The item must move up when its key goes down, and must move down when its key goes up. In this lab, a lower key always goes up, so the fix for this test is to call sift_up after the write. A complete set must handle both directions, so the fix checks which way the value moved.

void set(size_t i, int value) {
    bool went_up = value < data_[i];
    data_[i] = value;
    if (went_up) sift_up(i);
    else sift_down(i);
}

Apply this change to the set function and run the program again.

test 1 is_heap after pushes: PASS
test 2 pops in sorted order: PASS
        popped: 1 2 3 5 8 9
test 3 smallest after lowering key: 1 (expected 1)

All three tests pass. The complete fixed MinHeap class is the lab program with the three changes above.

Reading the rest of the code again

With the three bugs fixed, the code is correct for these inputs. A heap is not proven correct by three tests, so the next step is to try more inputs. The checker helps here. After each push or pop, call is_heap(), and if it returns false, print the array and stop. This finds a wrong heap at the first step where it goes wrong, which is much easier to read than a wrong final answer.

Look at the child-index formulas once more before you trust them. For a node at index i, the left child is at 2 * i + 1 and the right child is at 2 * i + 2. The parent of a node at index i is at (i - 1) / 2. A node at index 0 has no parent, so sift_up must stop at 0, which the while (i > 0) loop does. Each pair of indexes above can be checked with a small example. For example, the node at index 3 has parent (3 - 1) / 2, which is 1.

Common mistakes

Writing <= for a bound. An index into a vector of size n must be less than n. The bug above is left <= n. In a heap of 3 items after a pop, index 1 has a left child at index 3, and data_[3] is past the end.

Comparing the wrong way round. For a min heap, the parent must be smaller or equal to each child. A test such as data_[parent] >= data_[i] that stops the loop is the reverse of the rule. The output of the 5, 3, 1 trace shows the result: the root is not the smallest item.

Assuming the output is correct because it looks sorted. Test 2 in the lab prints a list, and a heap can give a list that is almost sorted. Use is_sorted or compare with std::sort on a copy, so the answer is checked by the computer.

Changing a key without moving the item. A key that changes in place leaves the heap in a state that the rules do not describe. Test 3 shows this. Any function that changes a value must fix the heap afterwards.

Subtracting from an unsigned index. The indexes in this lab have type size_t, which cannot be negative. Writing (i - 1) / 2 when i is 0 gives a very large number instead of -1. The while (i > 0) loop prevents this here, but a version that removes the check would read an index far outside the vector.

Mixing signed and unsigned in a loop. Compiling a loop like the one below gives a warning from -Wall:

for (int i = 0; i < v.size(); ++i) cout << v[i];

warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]

The warning is useful. Use size_t for the index, or int with a cast, so the comparison is between two values of the same kind.

Trusting an earlier run. A crash stops the program before buffered output is written. If a test line is missing, the test may still have run. Add std::endl or std::flush after a line you need to see before a crash.

Practice

Exercise 1. The sift_up function in the lab has the reversed comparison. Push 5, then 3, then 1 into a heap that uses this reversed comparison. What is the top, and what does pop return first?

Show the answer

The array after the three pushes is 5 3 1, as the trace above shows. The top is 5. The first pop returns 5, and the smallest item, 1, is not returned until later. The output of the pop is wrong because the root is not the smallest item.

Exercise 2. Inside sift_down, the bound is left <= n. After a pop leaves the heap with 3 items, which index is read one past the end, and in which call?

Show the answer

The read happens inside sift_down, after the moved item goes down to index 1. For example, push 1, 2, 3 and 4, then pop: the last item, 4, moves to the root and swaps with 2, so the loop now has i = 1. Then left is 2 * 1 + 1, which is 3, and the test left <= n is 3 <= 3, which is true. The code then reads data_[3], and a vector of size 3 has only indexes 0, 1 and 2. The fix is left < n.

Exercise 3. Look at this checker. Does it return true for the array {1, 3, 2, 0}? Explain the answer from the code.

bool is_heap(const vector<int>& data) {
    for (size_t i = 1; i < data.size(); ++i) {
        if (data[(i - 1) / 2] > data[i]) return false;
    }
    return true;
}

Show the answer

It returns false. The loop reaches i = 3, the parent index is (3 - 1) / 2, which is 1, and data[1] is 3. The test 3 > 0 is true, so the function returns false. The value 0 at index 3 is smaller than its parent, which breaks the rule.

Exercise 4. Write the body of set so that it works for both a lower key and a higher key. Test it on a heap made from the values 4, 7 and 6, first with set(2, 1) and then with set(0, 9). What is the smallest item after each change?

Show the answer

The body is the set function from step 3, which uses went_up to choose sift_up or sift_down. Run on the fixed class, the first change gives is_heap PASS, smallest 1. The second change, on a fresh heap made from 4, 7 and 6, gives is_heap PASS, smallest 6. Setting the root to 9 moves it down, and the smallest item becomes 6, which sits at index 2 before the change.

Exercise 5. Write a test that finds the bug in a heap without knowing the bug. The test should push random numbers, call is_heap() after each push, and stop at the first failure. Why is this better than checking only the final pops?

Show the answer

A loop of 100 pushes of random values calls is_heap() after each push and prints the array when it returns false. The first failing push points at the operation that broke the rule. A check only on the final pops says that the answer is wrong, but not when the heap became wrong. A check after each step shows the first place where the heap rule fails, which is where the bug is.

Summary

• A heap bug shows up as a crash, a failed checker, or a wrong output. Each needs a different first step.
• An index into a vector of size n must be less than n, so left <= n is an off-by-one error.
• For a min heap, the parent must be smaller or equal to each child. Check the comparison direction in sift_up and sift_down.
• A key changed in place must move to its correct place, and set must call sift_up or sift_down after the write.
• A checker such as is_heap(), called after every step, finds the first broken step.