Tracing the Priority Queue Sort

Let’s trace heapSortWithPriorityQueue. Here is an array, and we will use it as the running example for the rest of the chapter:

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

The first loop adds the values to the priority queue, starting at index 0. The priority queue is an ArrayHeap, so we draw its array. add 5 puts 5 at the root:

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

heap array
┌───┐
│ 5 │   size = 1
└───┘

add 3 places 3 after 5, and 3 swims up past 5:

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

heap array
┌───┬───┐
│ 3 │ 5 │   size = 2
└───┴───┘

add 8 places 8 at index 2. It is larger than its parent, 3, so it stays:

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

heap array
┌───┬───┬───┐
│ 3 │ 5 │ 8 │   size = 3
└───┴───┴───┘

The loop adds 1, 9, and 2 the same way. After the last add, the heap holds all six values, with the smallest, 1, at the root:

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

heap array
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 2 │ 5 │ 9 │ 8 │   size = 6
└───┴───┴───┴───┴───┴───┘

The second loop takes the values back out. At i = 0, peek returns 1, the smallest value. It goes into arr[0], and remove takes it out of the heap. The shaded slots of arr are the ones written so far. The slots after them still hold their old values, because the loop has not reached them yet:

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

heap array
┌───┬───┬───┬───┬───┐
│ 2 │ 3 │ 8 │ 5 │ 9 │   size = 5
└───┴───┴───┴───┴───┘

At i = 1, peek returns 2, the smallest value left. It goes into arr[1], and remove takes it out of the heap:

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

heap array
┌───┬───┬───┬───┐
│ 3 │ 5 │ 8 │ 9 │   size = 4
└───┴───┴───┴───┘

The loop goes on the same way, and each pass writes the smallest value left into the next slot. When the loop ends, the heap is empty and arr is sorted:

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

heap array
(empty)

Sorting in place

So heapsort is another $O (n lo g n)$ sorting algorithm, like merge sort. But the version we traced is not in place. It builds a whole priority queue that holds a copy of all $n$ elements, so it needs $O (n)$ auxiliary space on top of the array.

The heap is already stored in an array, the way the binary heap chapter stored it, and the input is an array too. Both hold the same $n$ values, only in different orders. So can one array do both jobs? It would hold the heap while the heap is built, and then hold the sorted values as the heap is emptied.