Emptying the Heap

We have a min-heap in the array, built in place:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 2 │ 5 │ 9 │ 8 │
└───┴───┴───┴───┴───┴───┘

Now we finish the sort by emptying the heap one element at a time.

Recall how remove works on a heap. It takes the root out, moves the last element up into the root, shrinks the heap by one, and sinks the new root back into place. The slot the last element leaves behind is now outside the heap, but still in the array, and that free slot is where the removed root can go. So instead of moving the last element up and throwing the root away, we swap the two, and then sink the new root.

The root is 1, the smallest. Swap it with the last element of the heap, 8, at index 5. The 1 is now in its final place, so we drop index 5 from the heap, and the heap is the first five entries. The shaded slots are the finished region:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 8 │ 3 │ 2 │ 5 │ 9 │░1░│   size = 5
└───┴───┴───┴───┴───┴───┘
  ↑
  i

Now sink the new root, 8. Its children are 3 at index 1 and 2 at index 2. The smaller is 2, and 8 is larger, so they swap. The children of index 2 would be at indices 5 and 6, both outside the heap, so the sink stops:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 2 │ 3 │ 8 │ 5 │ 9 │░1░│   size = 5
└───┴───┴───┴───┴───┴───┘
          ↑
          i

The second removal does the same. The root is now 2. Swap it with the last element of the heap, 9, at index 4, and drop index 4 from the heap:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 9 │ 3 │ 8 │ 5 │░2░│░1░│   size = 4
└───┴───┴───┴───┴───┴───┘
  ↑
  i

Sink 9. Its children are 3 and 8. The smaller is 3, so they swap:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 3 │ 9 │ 8 │ 5 │░2░│░1░│   size = 4
└───┴───┴───┴───┴───┴───┘
      ↑
      i

9 is at index 1 now. Its only child inside the heap is 5, at index 3. 5 is smaller, so they swap. Index 3 has no children inside the heap, so the sink stops:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 3 │ 5 │ 8 │ 9 │░2░│░1░│   size = 4
└───┴───┴───┴───┴───┴───┘
              ↑
              i

The third removal swaps the root, 3, with 9, at index 3, the last slot of the heap:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 9 │ 5 │ 8 │░3░│░2░│░1░│   size = 3
└───┴───┴───┴───┴───┴───┘
  ↑
  i

Sink 9. Its children are 5 and 8. The smaller is 5, so they swap. The children of index 1 would be at indices 3 and 4, outside the heap, so the sink stops:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 5 │ 9 │ 8 │░3░│░2░│░1░│   size = 3
└───┴───┴───┴───┴───┴───┘
      ↑
      i

The fourth removal swaps the root, 5, with 8, at index 2:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 8 │ 9 │░5░│░3░│░2░│░1░│   size = 2
└───┴───┴───┴───┴───┴───┘
  ↑
  i

Sink 8. Its only child is 9, and 8 is smaller, so 8 stays where it is.

The fifth removal swaps the root, 8, with 9, at index 1. That leaves a single element in the heap, 9, and it is already in place. The array is fully sorted:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 9 │ 8 │ 5 │ 3 │ 2 │ 1 │
└───┴───┴───┴───┴───┴───┘

The heap shrank from the right, one slot per removal, and the finished region grew from the right to fill the array.

The order is reversed

The result is sorted, but in the wrong direction: largest to smallest, when we wanted smallest to largest.

The first value we remove is the smallest, and it goes into the last slot. The last value we remove is the largest, and it ends up at the front.

To get ascending order, each removal has to return the largest element left, so the root has to hold the largest element. The heap has to be a max-heap. The selection sort from the quadratic sorting chapter works this way too. That version is the reverse of the one in the dynamic array chapter: it selects the largest remaining element and swaps it into the last unsorted slot.