Lab: Priority Queues

Beware of the dreaded PQMonster.java.

Drawing by Mary P

Background

In a stack, we can only peek at or remove the last element added. In a queue, we can only peek at or remove the first element added. In a priority queue, we can only peek at or remove the minimum element. Like a stack or a queue, a priority queue may contain duplicate values.

We'll represent priority queues using the following interface. Notice that the elements must implement Comparable.

public interface PriorityQueue<E extends Comparable<E>>

{

void add(E obj);

E removeMin(); // removes and returns the minimum element (precondition: not empty)

E peekMin(); // returns the minimum element (precondition: not empty)

boolean isEmpty();

}

Here is a sample usage of the PriorityQueue interface.

PriorityQueue<Integer> pq = /* construction not shown */;

pq.add(5);

pq.add(3);

pq.add(1);

pq.add(2);

pq.add(8);

pq.add(1);

System.out.println(pq.removeMin()); // prints: 1

System.out.println(pq.removeMin()); // prints: 2

System.out.println(pq.removeMin()); // prints: 3

System.out.println(pq.removeMin()); // prints: 5

System.out.println(pq.peekMin()); // prints: 8

System.out.println(pq.isEmpty()); // prints: false

pq.removeMin();

System.out.println(pq.isEmpty()); // prints: true

Assignment

Download pqlab.zip.

Open PriorityQueue.java. Inside, you'll see the PriorityQueue interface.

Open PriorityQueueImpl.java. You will write all code for this assignment in this file. When finished your PriorityQueueImpl class will correctly implement all methods required by the PriorityQueue interface. Your grade will depend on how efficient these methods are.

To earn a 90%:
isEmpty: O(1)
add: O(1)
peekMin: O(1)
removeMin: O(n)
Hint: First, implement PriorityQueue in the simplest way you can think of. Then go back and figure out how to make your running times match the ones listed above.

OR, to earn 95%:
isEmpty: O(1)
add: O(1) expected, O(log n) worst-case
peekMin: O(1)
removeMin: O(log n)

And to earn 5% more:
Implement an in-place sorting algorithm with worst-case O(n log n) time: heap sort.

public static <E extends Comparable<E>> void heapSort(E[] array)

Throughout the algorithm, the left part of the array represents a max-heap.

In the first phase of heapsort, the 1st element is added to the max-heap, then the 2nd, 3rd, etc., until all elements are arranged in a max-heap, as in the following example.

1, 8, 3, 4, 5, 6, 7, 2

8, 1, 3, 4, 5, 6, 7, 2

8, 4, 3, 1, 5, 6, 7, 2

8, 5, 3, 1, 4, 6, 7, 2

8, 5, 6, 1, 4, 3, 7, 2

8, 5, 7, 1, 4, 3, 6, 2

8, 5, 7, 2, 4, 3, 6, 1

In the second phase of heapsort, the maximum is removed from the heap and stored at the last index, then the new maximum is removed and stored at the second-to-last index, and so on, until the max-heap is empty and the array has been sorted.

7, 5, 6, 2, 4, 3, 1, 8

6, 5, 3, 2, 4, 1, 7, 8

5, 4, 3, 2, 1, 6, 7, 8

4, 2, 3, 1, 5, 6, 7, 8

3, 2, 1, 4, 5, 6, 7, 8

2, 1, 3, 4, 5, 6, 7, 8

1, 2, 3, 4, 5, 6, 7, 8

The first phase adds the n elements, each in worst case O(log n) time, while the second phase removes the n elements, each in O(log n) time. Therefore, heapsort runs in worst-case O(n log n) time.