Sorting with a Priority Queue

The questions in this section use this priority queue interface:

public interface PriorityQueue<T extends Comparable<T>> {
  void add(T item);  // adds item; throws IllegalArgumentException if item is null
  T peek();          // returns the highest-priority item; throws NoSuchElementException if empty
  void remove();     // removes the highest-priority item; throws NoSuchElementException if empty
  int size();        // returns the number of items
}

ArrayHeap<T> implements PriorityQueue<T> as a binary min-heap stored in an array, so the smallest item has the highest priority. It has a no-argument constructor. Its add and remove are $O (lo g n)$ , and its peek is $O (1)$ .

Exercise

Write the method below. It must sort arr in ascending order by passing its values through an ArrayHeap.

// Sorts arr in ascending order. Assumes arr is not null.
public static void heapSortWithPriorityQueue(int[] arr) {

}

Solution

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();
  }
}

Solution

The running time is $O (n lo g n)$ . The method makes $n$ calls to add and $n$ calls to remove, and each call is $O (lo g n)$ .
The auxiliary space is $O (n)$ . The priority queue holds a copy of all $n$ values.

Solution

The priority queue speeds up finding the smallest element that has not been placed yet. Selection sort scans the unsorted part of the array for it, which is $O (n)$ per pass.