Priority Queue

Recall queues also called FIFO? Standard queues prioritize temporally; like standing in a line, first come first serve.  Priority queues are a generalization of the standard queue, and prioritize by a key.

Priority queues contain entries = {keys, values}

Examples

• Seating on a fill plane

• Operating system job control

• Patient serving in the Emergency ward

• Securities exchanges:

  • Bids: maximum buy price

• Asks: minimum sell price

What would be the values and keys above?

Interfaces

/** Interface for a key-value pair entry **/
public interface Entry {
  public Object key();
  public Object value();
}

The keys and values can be equal. 

We also need same way to compare keys.  Another class Comparator.   Mathematically the comparator is a total ordering relation

Total ordering

≤ (meaning less or equal) has properties:

• Reflexivity : k ≤ k

• Antisymmetry: if k₁ ≤ k₂ and k₂ ≤ k₁, then k₁ = k₂

• Transitivity: if k₁ ≤ k₂ and k₂ ≤ k₃, then k₁ ≤ k₃

Java has Comparator interface with only one method;

int compareTo(Object o), 

Known implementing classes are Byte, Character, Double, File, Float, Long, ObjectStreamField, Short, String, Integer, BigInteger, BigDecimal, Date, and  CollationKey.

Example comparator class

/** Comparator for 2D points under the standard lexicographic order. */
public class Lexicographic implements Comparator {
  int xa, ya, xb, yb;
  public int compare(Object a, Object b) throws ClassCastException {
    xa = ((Point2D) a).getX();
    ya = ((Point2D) a).getY();
    xb = ((Point2D) b).getX();
    yb = ((Point2D) b).getY();
    if (xa != xb)
      return (xb - xa);
    else
      return (yb - ya);
  }
}

Priority Queue

/** Interface for the priority queue ADT */
public interface PriorityQueue {
  /** Returns the number of items in the priority queue. */
  public int size();
  /** Returns whether the priority queue is empty. */
  public boolean isEmpty();
  /** Returns but does not remove an entry with minimum key. */
  public Entry min() throws EmptyPriorityQueueException;
  /** Inserts a key-value pair and return the entry created. */
  public Entry insert(Object key, Object value) throws InvalidKeyException;
  /** Removes and returns an entry with minimum key. */
  public Entry removeMin() throws EmptyPriorityQueueException;
}

Implementation

Listed based, sorted and unsorted

Sorted based insert: the entries into the list based on the key order, and therefore the minimum key entry location is know.

Unsorted: must search for the minimal key entry in the list.  

Comparison of Cost

Priority Queue Sort

Algorithm: PQSort:(Sequence S, PriorityQueue Q)

for all Positions p  in S do
     Item i = S.remove(p)
     Q.insert(i)

while ( !Q.isEmpty() ) do
     Position p = Q.removeMin()
     S.insertLast(p)

We can use either sorted or unsorted list priority queue. For both the complexity or cost is O(n²)
Space requirements? In place?