Flat Designs

The questions in this section are about implementing a min priority queue with this interface, where the smallest element has the highest priority:

public interface PriorityQueue<T extends Comparable<T>> {
  void add(T item);   // inserts item
  T peek();           // returns the smallest item
  void remove();      // removes the smallest item
  int size();
}

Each design below keeps the $n$ elements in a single sequence, either a linked list or an array, and keeps a count of them, so size is $O (1)$ .

Solution

add is $O (1)$ : it inserts the new element at the head. peek is $O (n)$ : the smallest element could be anywhere, so it scans the whole list. remove is $O (n)$ : the same scan finds the node, and the $O (1)$ unlink does not change the total.

Solution

add is amortized $O (1)$ : it appends after the last filled slot, and the array resizes only when it is full. peek is $O (n)$ : it scans the filled part of the array. remove is $O (n)$ : it scans to find the smallest element, then moves the last element into that slot in $O (1)$ .

Solution

In the last filled slot, so the array is sorted from largest to smallest. peek is $O (1)$ : it reads the last filled slot. remove is $O (1)$ : it clears the last filled slot and nothing shifts. add is $O (n)$ : binary search finds the position in $O (lo g n)$ , but every element after that position shifts one slot right.

Solution

An unsorted design does no work on add, so the smallest element could be anywhere, and peek and remove have to scan for it. A sorted design keeps the smallest element in a known place, but add has to keep the sequence sorted, which means shifting elements to make room.