Push, pop and heapify

Why this matters

A heap is only useful if you can keep it correct while items arrive and leave. In the last lesson you learned the shape of a heap and how to find parents and children in an array. Now you will make the heap change. You will insert a new value and keep the heap-order rule true. You will remove the smallest value and repair the tree. You will also turn an unsorted array into a heap in one pass.

These three actions are the core of every heap-based program. The standard library has a heap container, which you will meet in the next lesson, but that container runs exactly the operations you will write here. If you understand push, pop and heapify by hand, the library will never feel like magic. You will also be able to explain your choices in an interview, which is where this material matters most.

The idea is simple. Every change touches one path in the tree, from a leaf to the root or from the root down to a leaf. Because a heap has about log n levels, each change costs about log n steps. This lesson builds that idea from the ground up, with programs that you can run.

The shape of the problem

Recall the two rules from the first lesson. The tree is complete, so every level is full except possibly the last, which fills from the left. And in a min-heap each parent is less than or equal to each child.

An insert breaks one of these rules, and a removal breaks another. Let us see how.

For an insert, we add the new value at the end of the array. That keeps the tree complete, because the array's last slot is the next leaf position in level order. But the new value might be smaller than its parent. The heap-order rule is now broken on one link, and only that link. Every other parent-child pair was fine before, and the new value is only related to one parent above it.

For a removal, we want the smallest value, which sits at the root. We take it out. Now the root is empty, and we have a hole at the top. We cannot leave a hole, because the tree must stay complete. So we move the last value of the array into the root. That keeps the shape. But the moved value is probably big, so it may be larger than one or both of its new children. Again, the heap-order rule is broken on a path from the top down.

The fix in both cases is local. We move the troublemaking value along one path until it fits. Let us name the two moves.

• Sift-up moves a value up the tree while it is smaller than its parent. It is used after a push.
• Sift-down moves a value down the tree while it is larger than its smaller child. It is used after a pop.

The word "sift" means to pass something through a sieve, slowly. Both moves are slow and careful, one step at a time, and they stop as soon as the value is in the right place.

An everyday picture of sift-up

Imagine a hand of playing cards sorted from smallest at the top of the stack to largest at the bottom. You pick up a new card and drop it on the bottom of the stack. If it is smaller than the card above, you swap them. You repeat that until the card above is smaller than the new one, or until it reaches the top. The stack is sorted again after a few swaps, and you touched only the cards on the path you passed.

A min-heap insert works the same way, but the cards are arranged as a tree, and the path goes through the parent of each position. Each swap moves the new value up one level, and the parent moves down one level to take its place.

An everyday picture of sift-down

Now think of a team with a captain at the top. Suppose the captain retires. The easiest replacement is the last person who joined the team. You put that person in the captain's seat. But the new captain may be weaker than the two people directly below, so you swap them with the better of the two substitutes, the one with the smaller score in a min-heap. You keep doing that until the person is not weaker than anyone below. Each swap moves the replacement one level down.

That is sift-down. The new value starts at the top, and it sinks until both of its children are at least as large as it is.

Insert: sift-up in detail

Here is the procedure written in words first.

1. Append the new value to the end of the array. The tree is still complete.
2. Let i be the index of the new value.
3. While i is greater than 0, compute the parent index p = (i - 1) / 2.
4. If the parent value is less than or equal to the value at i, stop. The heap-order rule holds.
5. Otherwise swap the value at i with the value at p, and set i = p. Go back to step 3.

Step 4 is where the heap rule is checked. Stopping on "less than or equal" keeps the rule in its weakest form, which is all a heap needs. Equal values are allowed to sit in either order.

Here is a step-by-step trace. We start with the empty heap and push the values 5, 3, 8, 1. We write the array after each push.

1. Push 5. The array is [5]. There is no parent, so we stop.
2. Push 3. Append it: [5, 3]. Index 1 has parent index 0, which holds 5. Since 5 is greater than 3, swap them: [3, 5]. Index 0 has no parent, so we stop.
3. Push 8. Append it: [3, 5, 8]. Index 2 has parent index 0, which holds 3. Since 3 is at most 8, we stop. The array stays [3, 5, 8].
4. Push 1. Append it: [3, 5, 8, 1]. Index 3 has parent index 1, which holds 5. Since 5 is greater than 1, swap: [3, 1, 8, 5]. Now index 1 has parent index 0, which holds 3. Since 3 is greater than 1, swap: [1, 3, 8, 5]. Index 0 has no parent, so we stop.

After the four pushes, the root holds 1, the smallest value, as it should. The array is not sorted, but every parent is at most its children. Check it: 1 is at most 3 and 8, and 3 is at most 5. Good.

Notice how many swaps happened. Step 4 needed two swaps because the new value rose from the bottom to the top. The number of swaps in one insert can be at most the height of the tree, which is about log n.

Three rows of an array showing 1 moving up past 5 and then past 3 during a push

Remove: sift-down in detail

Removal of the smallest value is called pop in heap terms. It works in four moves.

1. Save the value at the root. This is the answer.
2. Copy the last value of the array into the root position. Then remove the last slot.
3. Let i = 0. Look at the children of i: 2 * i + 1 and 2 * i + 2. Keep only those that exist.
4. Among i and its existing children, find the smallest value. If i already holds the smallest, stop.
5. Otherwise swap i with the smallest child, set i to that child's index, and go back to step 3.

The check in step 4 is the heart of sift-down. You must compare the value with both children and pick the smaller child, not the first one you see. If you swap with the left child when the right child is smaller, the right child may end up below a larger parent. That is a bug you will meet in the mistakes section.

Here is a trace. Start with the heap [1, 3, 2, 5, 4, 6, 7]. That is a valid min-heap: the root is 1, and each parent is at most its children. Now pop.

1. Save the root 1 as the answer.
2. Move the last value 7 to the root and remove the last slot: [7, 3, 2, 5, 4, 6].
3. Index 0 holds 7. Its children are index 1 with 3 and index 2 with 2. The smaller child is 2 at index 2. Since 2 is less than 7, swap: [2, 3, 7, 5, 4, 6]. Now i = 2.
4. Index 2 holds 7. Its children are indexes 5 and 6. Index 5 holds 6. Index 6 does not exist, because the array has only six values. The smaller child is 6, and 6 is less than 7, so swap: [2, 3, 6, 5, 4, 7]. Now i = 5.
5. Index 5 holds 7. It has no children, because 2 * 5 + 1 = 11 is past the end. Stop.

The result is [2, 3, 6, 5, 4, 7]. The value popped was 1. Check the heap rule: 2 is at most 3 and 6, 3 is at most 5 and 4, and 6 is at most 7. Yes, a valid heap.

Sift-down can walk all the way from the root to a leaf, which is the longest path. That path has about log n steps. The pop costs O(log n).

Three rows of an array showing the last value moved to the root and sifted down during a pop

Step through the visualizer below to watch a pop move the last value to the root and sink it down. Watch which child the value swaps with each time, and check that the smaller child always wins.

Heap sort with a class

Now we can put the pieces together in code. The class below is a complete min-heap. It stores its values in a vector, and it has push, pop, top, size and empty. The helper methods siftUp and siftDown do the moves described above. The class is marked private for those helpers, because a user of the heap should not call them directly.

The first program uses the class to push values and print the array after each push. The input is six values, which you type into the Input box:

Input to type in the Input box:

6
5 3 8 1 9 2

The output is:

push 5 -> [5]
push 3 -> [3, 5]
push 8 -> [3, 5, 8]
push 1 -> [1, 3, 8, 5]
push 9 -> [1, 3, 8, 5, 9]
push 2 -> [1, 3, 2, 5, 9, 8]
top is 1

Check the push of 2 against the rules. The array before it was [1, 3, 8, 5, 9]. The value 2 goes to index 5, whose parent is index 2, holding 8. Since 8 is greater than 2, swap, giving [1, 3, 2, 5, 9, 8]. Index 2 has parent index 0, holding 1. Since 1 is at most 2, stop. Matching the trace makes you confident in the code.

Heap sort by popping

If you pop every value out of a min-heap, you get the values in ascending order. That is the basic idea of heap sort, a sorting method that runs in O(n log n) time. Each of the n pops costs O(log n), so the total is O(n log n).

The next program reads values, pushes them all, and pops them all. It also demonstrates the error you get when you pop an empty heap. Type this into the Input box:

7
4 9 1 7 3 3 0

The output is:

0 1 3 3 4 7 9
caught: pop() on empty heap

The values come out sorted, including the two copies of 3. The last line shows that the heap refuses to pop from an empty heap and throws an error. Catching the error with try and catch lets the program print a clear message instead of crashing.

Building a heap all at once: heapify

Pushing values one at a time costs O(n log n) in total, because each push may sift up about log n levels. There is a faster way when you already have all the values in an array. It is called heapify, and it builds the heap in O(n) time.

The method runs sift-down on every node that has a child, starting from the last one that has a child and moving back to the root. The last node with a child is at index n / 2 - 1, because the leaves start at index n / 2, as we saw in the first lesson. So the loop is:

1. For i from n / 2 - 1 down to 0, call sift-down on index i.

Why does this work? When you reach index i, both of its subtrees are already heaps, because every index after i in the loop has been fixed. Sift-down on i then fixes the rule at i by moving its value down into a heap that is already valid below it.

Why is it O(n) and not O(n log n)? Most nodes are near the bottom. Half of the nodes are leaves, and they do nothing. A quarter of the nodes sit one level up and may sift down by one step. An eighth sit two levels up and may sift by two steps. The total work is the sum of those small costs, and that sum is at most n. Heapify is cheap because the expensive long paths belong to very few nodes.

Here is the heapify code, with a counter that counts swaps so you can see the work:

Type this into the Input box:

6
9 4 7 1 8 2

The output is:

before: [9, 4, 7, 1, 8, 2]
after: [1, 4, 2, 9, 8, 7]
swaps: 4

Trace the loop by hand. The loop starts at i = 6 / 2 = 3, so it calls sift-down on index 2, then 1, then 0. Index 2 holds 7 with child 2 at index 5. They swap: [9, 4, 2, 1, 8, 7]. Index 1 holds 4 with children 1 and 8. The smaller child is 1, so swap: [9, 1, 2, 4, 8, 7]. Index 0 holds 9 with children 1 and 2. The smaller is 1. Swap: [1, 9, 2, 4, 8, 7]. Now index 1 holds 9 with children 4 and 8. The smaller is 4. Swap: [1, 4, 2, 9, 8, 7]. Index 3 holds 9 and has no children, since 2 * 3 + 1 = 7 is past the end. Four swaps in total, and the result matches the output.

Pushing the same six values one at a time also ends at [1, 4, 2, 9, 8, 7] here. That is not always true. The two methods can build different arrays from the same values, and both arrays are valid heaps, because the heap rule does not fix one arrangement.

A randomized test: trust, but check

Testing a data structure by reading the code is not enough. A common method is to test it against a simple, trusted version. Here the trusted version is multiset, a sorted container from the standard library. Every time the heap pops a value, the program checks that the value equals the smallest value in the multiset. The random numbers come from a small generator that you can reproduce, so every run does the same work.

The generator uses the formula seed * 1103515245 + 12345, a classic linear congruential generator. You do not need to know why it works. You only need to know that it gives a fixed sequence of numbers from a fixed starting seed. The program runs 200 rounds, and each round mixes pushes and pops.

The program has no input. The output is:

checks: 5287
failures: 0
caught: top() on empty heap

If a single pop returned the wrong value, failures would count it. A result of 0 failures over thousands of checks is good evidence the heap works. This style of testing, with a slow obvious version as the judge, is one of the most useful habits you can build. It catches bugs that a reader would miss.

What happens inside

Let us follow one push in the computer. The call h.push(5) runs the method. It calls data.push_back(5), which adds a value at the end of the vector. If the vector has no free space left, it allocates a larger block, copies the old values, and frees the old block. The growth is done in big steps, so the average cost of push_back is O(1). Next, siftUp runs with the index of the new value. Each loop step computes a parent index with arithmetic, reads two values from the array, and maybe swaps them. The swap writes two values into memory that sit next to each other, which is fast on a modern processor.

The loop ends when it reaches a parent that is small enough, or when the index reaches 0. The method then returns. Nothing in the heap is a pointer, so there is nothing to free when a value is removed. pop_back shrinks the logical size of the vector and keeps its capacity for later pushes.

A pop runs the same kind of loop, but it moves downward and reads two children at each step. The work at each level is constant, so the whole pop is proportional to the height of the tree.

Complexity: the costs in one table

Push is O(log n) in the worst case, not on average. A sorted sequence of pushes that always goes to the top makes every push walk the full height. A random sequence usually stops early, so the average push is O(1) for random data. Interviewers often ask about this difference, so state the worst case unless the question asks for the average.

Space use is O(n) for the array. Heap operations use O(1) extra space, because the loops only hold a few indexes.

Why sift-down must pick the smaller child

Sift-down has a rule that is easy to say and easy to break. It swaps the moving value with the smaller of its two children, and only when that child is smaller than the value. The reason is simple. The child that moves up takes the parent's place, and both children stay under that place. The new parent must therefore be no larger than either child. If the larger child moved up, the smaller child would sit below a larger value, and the heap rule would break.

Take a parent holding 9 with children 4 and 2, stored as [9, 4, 2]. Suppose the value 9 must sink. There are two choices.

• Swap with the left child 4. The result is [4, 9, 2]. The root is 4, but its right child is 2, which is smaller. The heap rule is broken.
• Swap with the smaller child 2. The result is [2, 4, 9]. The root is 2, and both children are at least 2. The heap rule holds.

Those two results differ in one comparison, and that comparison is the whole rule. In code, you compare the parent value with both children and pick the smallest of the three. The check right < n && data[right] < data[smallest] in the class is that second comparison. Leave it out and the first result happens.

What the costs look like in practice

The big-O bound hides the real numbers, so here are some. A push into a heap of one million values walks at most about twenty levels, because 2^20 is about one million. So a push makes at most twenty swaps. A pop walks down at most twenty levels, and at each level it compares two children, so it makes at most about forty comparisons. A modern processor finishes that in well under a microsecond.

Heapify on the same million values does less work than a million pushes. Each push may climb twenty levels, which is up to twenty million steps in the worst case. Heapify's total is at most about one million steps, because most nodes sink only a level or two. That difference is the reason to build from an array when you have all the values up front, and to push one at a time only when values really arrive over time.

Common mistakes and the messages they produce

Mistake 1: stopping sift-down too early

A common error is to compare the value only with the left child, as in this broken code:

if (left < n && data[left] < data[i]) {
    swap(data[i], data[left]);
    i = left;
}

This code never looks at the right child. Take the heap [1, 9, 2] and pop. The last value 2 moves to the root: [2, 9]. The left child 9 is larger than 2, so the code stops. Looks fine. Now take [1, 9, 2, 5, 6]. The last value 6 moves to the root: [6, 9, 2, 5]. The left child 9 is greater than 6, so no swap, and the code stops. But the right child 2 is smaller than 6, and the heap rule is broken: index 0 holds 6, larger than index 2, which holds 2. The fix is to compare with both children and pick the smaller, as the real code does.

Mistake 2: forgetting to check the size before reading

In pop, the code must check that the heap is not empty before it reads data[0]. Without the check, the read goes past the end of the vector. Modern C++ often does not stop the program right away, so you may see a random number instead of an error. With the check in place, the error is clear:

terminate called after throwing an instance of 'std::runtime_error'
  what():  pop() on empty heap

The first line names the type of error, std::runtime_error, and the second line gives the text you wrote in the throw. If you do not catch the error, the program ends with this message. If you catch it, as in the heap sort program, you can print your own message and continue.

Mistake 3: sifting with the wrong size

In pop, the code moves the last value to the root and then calls pop_back, and only after that does it call siftDown. If you call siftDown before pop_back, the function still sees the old size. It may then compare with a child that is no longer in the heap, a value that was just moved. Always shrink the vector before the sift, so siftDown reads the current size, which is what the real code does.

Mistake 4: a comparison that loops forever

If the sift-up loop compares with the wrong direction, or forgets to set i = parent, the loop may never end. The symptom is a program that runs at 100 percent of one processor and never prints. The cure is to keep the loop variable changing on every pass, which is why each path in the code updates i.

Mistake 5: equal values and strict comparisons

Using < where you need <= in the sift-up check does no harm for correctness. It only does extra swaps. But using <= where you need < in a sift-down can cause a swap with an equal child, which again only costs time. The rule of thumb is simple: a swap is needed only when the child is strictly smaller than the parent. The code in this lesson follows that rule.

Debugging walkthrough: find the first broken push

Suppose you wrote a heap and a test shows that the top value is wrong after some pushes. You do not know which push caused it. A good method is to check the heap rule after every operation, and stop at the first failure.

Add a function that walks every parent-child pair and returns the index of the first bad child, or -1 if the heap is valid:

int firstBadChild(const vector<int>& a) {
    for (size_t i = 1; i < a.size(); i++) {
        size_t parent = (i - 1) / 2;
        if (a[parent] > a[i]) return (int)i;
    }
    return -1;
}

Call it after each push in your test loop, and print the value you pushed when the result is not -1. The push that broke the heap is the first one that causes the check to fail. Then trace that push with the sift-up steps by hand. This is quicker than reading the whole class, because you only need to explain one operation.

Notice that the check costs O(n) each time. Use it only while you debug, and remove it when the heap is correct, because checking after every push turns an O(log n) operation into an O(n) one.

Edge cases you should test

• A heap with one value. Pop returns that value, then the heap is empty. Sift-down is not called.
• Two values. Pushing a smaller value second moves it to the root. Popping then returns the smaller value and moves the larger value to the root.
• Duplicate values. Five copies of 4 should pop as five fours. The heap rule allows equal values in either order, so the results should match a sorted list.
• An already sorted sequence pushed in ascending order. Each push stops immediately, because each new value is larger than its parent. This is the fastest case for pushing.
• A sequence pushed in descending order. Each push sifts all the way to the root, which is the worst case for pushing. Try it and count the swaps.
• Heapify on an empty array or one value. The loop for (size_t i = n / 2; i > 0; i--) does nothing when n is 0 or 1, which is correct.

Notice the heapify loop. For n = 1, n / 2 is 0, so the loop never runs. Written as i = n / 2 - 1 the same loop would underflow on size_t, which is a mistake you already met in the first lesson.

Interview questions you should be ready for

Why is pushing n values one at a time O(n log n), but heapify O(n)? Push may sift all the way up for each value. Heapify sifts most nodes only a short distance, because most nodes are near the bottom, so the sum of the distances is about 2n.

Why does sift-down compare with both children? It must put the smallest of the three values at the top of the subtree. Comparing with only one child can leave a smaller child below a larger parent.

Is pop always O(log n)? Yes in the worst case. The path length is bounded by the height of the tree, and the work at each level is constant.

What is the state after pop on a heap of one value? The heap is empty. The code takes the value, copies the last value to the root (the same value), removes the last slot, and skips sift-down because the heap is empty.

Can two different arrays both be valid min-heaps for the same set of values? Yes. The heap rule does not fix one arrangement. The heap built by pushes and the heap built by heapify can differ, and both are correct.

Practice

1. Push the values 4, 2, 7, 1 into an empty min-heap by hand. Write the array after each push.

2. Pop once from the heap [1, 3, 2, 5, 4, 6, 7] by hand, and write the array after the pop. Check that it is still a valid heap.

3. Build a heap from the array [5, 4, 3, 2, 1] with heapify, by hand. Write the array after each sift-down.

4. Change the program that pushes values so it prints the array after pops too. Type 7 values and check the result is a valid heap after each pop.

5. Write a method int secondSmallest() for the MinHeap class. It must not pop anything. Explain why it is not always at index 1.

6. Make siftDown buggy by checking only the left child. Run the random test program with the buggy version. Does failures become nonzero?

7. Write a program that reads n and n values, builds a heap with pushes, and then prints the number of swaps. Compare that number with the number of swaps that heapify makes on the same input.

8. What is the time cost of heap sort on an already sorted array of one million values? Explain in two sentences.

9. Explain in your own words why heapify starts at index n / 2 - 1 and not at the last index n - 1.

10. Add a peekAll method that returns the values in sorted order without changing the heap. Is it efficient? Explain.

What you now know

• A push appends a value at the end of the array and sifts it up while it is smaller than its parent. It costs O(log n).
• A pop saves the root, moves the last value to the root, shrinks the array, and sifts the new root down, always toward the smaller child. It costs O(log n).
• Heapify builds a heap from an array in O(n) by sifting down every node that has a child, starting from the last one.
• Heap sort pops every value and gives a sorted result in O(n log n).
• Test a heap against a trusted slow version, and check the heap rule after each operation while you debug.
• Watch for empty heaps, sift-down that compares with only one child, and size_t arithmetic on zero.