# Priority Queues

A priority queue is an implementation of a queue where each item stored has a priority. The items with the highest priority are moved to the front of the queue to leave first. A priority queue takes a key along with a value, where the key is used as the priority of the item.

public interface PriorityQueue<K,V>{
int size();
boolean isEmpty();
void insert(K key, V value); //inserts a value into the queue with key as its priority
V removeMin(); //removes the entry with the lowest key (at the front of the queue)
V min(); //returns but not removes the smallest key entry (peek)
}


### Entry Objects

• To store a key-value pair, a tuple/pair-like object is needed
• An Entry<K,V> object is used to store each queue item
• Key is what is used to defined the priority of the item in the queue
• Value is the queue item
• This pattern is similar to what is used in maps
public class Entry<K,V>{
private K key;
private V value;

public Entry(K key, V value){
this.key = key;
this.value = value;
}

public K getKey(){
return key;
}

public V getValue(){
return value;
}

}


## Total Order Relations

• Keys may be arbitrary values, so they must have some order defined on them
• Two entries may also have the same key
• A total order relation is a mathematical concept which formalises ordering on a set of objects where any 2 are comparable.
• A total ordering satisfies the following properties
• or
• Comparability property
• If , then
• Transitive property
• If and , then
• Antisymmetric property
• Reflexive property

## Comparators

• A comparator encapsulates the action of comparing two objects with a total order declared on them
• A priority queue uses a comparator object given to it to compare two keys to decide their priority
public class Comparator<E>{
public int compare(E a, E b){
if(a < b)
return -1;
if(a > b)
return 1;
return 0;
}
}


## Implementations

### Unsorted List-Based Implementation

A simple implementation of a priority queue can use an unsorted list

• insert() just appends the Entry(key,value) to the list
• time
• removeMin() and min() linear search the list to find the smallest key (one with highest priority) to return
• Linear search takes time

### Sorted List-Based Implementation

To improve the speed of removing items, a sorted list can instead be used. These two implementations have a tradeoff between which operations are faster, so the best one for the application is usually chosen.

• insert() finds the correct place to insert the Entry(key,value) in the list to maintain the ordering
• Has to find place to insert, takes time
• As the list is maintained in order, the entry with the lowest key is always at the front, meaning removeMin() and min() just pop from the front
• Takes time

## Sorting Using a Priority Queue

The idea of using a priority queue for sorting is that all the elements are inserted into the queue, then removed one at a time such that they are in order

• Selection sort uses an unsorted queue
• Inserting items in each time takes time
• Removing the elements in order
• Overall time
• Insertion sort uses a sorted queue
• Runtimes are the opposite to unsorted