Sorting with a Priority Queue

The last two chapters built the priority queue and then the binary heap. The heap is the implementation where add and remove are both $O (lo g n)$ , peek is $O (1)$ , and a removal always takes out the smallest element. In this chapter, we use the heap to sort an array.

Recall selection sort. It was the first sorting algorithm we wrote, back in the dynamic array chapter. Selection sort finds the smallest element in the array and moves it to the front, then finds the smallest of what remains and moves it into the next position, and continues until everything is placed.

The asymptotics chapter found where selection sort spends its time. The swap that moves each element into place is $O (1)$ . Finding the minimum is the expensive part: each pass scans the unsorted part of the array for the smallest element, and about $n$ of those linear scans add up to $O (n^{2})$ .

On every pass, selection sort needs the smallest element not yet placed. That is what a priority queue gives you. Selection sort spends $O (n)$ to find that element. The binary heap finds it in $O (1)$ and removes it in $O (lo g n)$ .

Add all $n$ elements to a priority queue. Then take them back out one at a time, writing each into the array from left to right. Each time, peek returns the smallest element still in the queue and remove takes it out, so the values come out in increasing order and land in the array sorted.

public static void heapSortWithPriorityQueue(int[] arr) {
  PriorityQueue<Integer> pq = new ArrayHeap<>();
  for (int i = 0; i < arr.length; i++) {
    pq.add(arr[i]);
  }
  for (int i = 0; i < arr.length; i++) {
    arr[i] = pq.peek();
    pq.remove();
  }
}

What it costs

Filling the queue takes $n$ calls to add, and emptying it takes $n$ calls to remove. Each of those calls is $O (lo g n)$ . So the sort is $O (n lo g n)$ , which beats selection sort’s $O (n^{2})$ .

Any priority queue would sort this way. But of the implementations we built, only the binary heap makes it $O (n lo g n)$ . That is why the sort is called heapsort.

The next section traces the sort on an example array.