Priority Queues
Contents
- Priority Queues
- Implementations
- Unsorted List
- Sorted List
- Array-Based Heap
- Tree-Based Heap
- Priority Queue Sort
- Selection Sort
- Insertion Sort
- Heap Sort
Time Complexity
| Method | Unsorted list | Sorted list | Array heap | Linked-tree heap |
|---|---|---|---|---|
| size | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ |
| isEmpty | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ |
| min | $O(n)$ | $O(1)$ | $O(1)$ | $O(1)$ |
| insert | $O(1)$ | $O(n)$ | $O(\log n)^*$ | $O(\log n)$ |
| removeMin | $O(n)$ | $O(1)$ | $O(\log n)^*$ | $O(\log n)$ |
* = amortized complexity
Priority Queues
- A priority queue is a tree-based data structure consisting of key-value pairs.
- A priority queue uses the whatever in, priority-out principle.
- A priority queue has two major operations: insert and delete-min.
Applications
- Flight queue with customer priority
- Call center queue with customer priority
- Technical support queue with customer priority
- Vaccination queue with citizen priority
- All applications of sorting
Priority Queue ADT
| Method | Functionality |
|---|---|
| insert(k, v) | Creates an entry with key k and value v in the priority queue. |
| min() | Returns (but does not remove) a priority queue entry (k,v) having minimal key; returns null if the priority queue is empty. |
| removeMin() | Removes and returns an entry (k,v) having minimal key from the priority queue; returns null if the priority queue is empty. |
| size() | Returns the number of entries in the priority queue. |
| isEmpty() | Returns a boolean indicating whether the priority queue is empty. |
Operations
| Method | Return value | Priority queue contents |
|---|---|---|
| insert(5,A) | $\{$ (5,A) $\}$ | |
| insert(9,C) | $\{$ (5,A), (9,C) $\}$ | |
| insert(3,B) | $\{$ (3,B), (5,A), (9,C) $\}$ | |
| min() | (3,B) | $\{$ (3,B), (5,A), (9,C) $\}$ |
| removeMin() | (3,B) | $\{$ (5,A), (9,C) $\}$ |
| insert(7,D) | $\{$ (5,A), (7,D), (9,C) $\}$ | |
| removeMin() | (5,A) | $\{$ (7,D), (9,C) $\}$ |
| removeMin() | (7,D) | $\{$ (9,C) $\}$ |
| removeMin() | (9,C) | $\{$ $\}$ |
| removeMin() | null | $\{$ $\}$ |
| isEmpty() | true | $\{$ $\}$ |
Priority Queue ADT $\rightarrow$ Unsorted List Implementation
- We use a PositionalList which in turn uses DLL.
- insert method inserts a key-value entry at the end of the list in $O(1)$ time.
- min or removeMin requires scanning the entire list in $O(n)$ time.
| Method | Unsorted list |
|---|---|
| size | $O(1)$ |
| isEmpty | $O(1)$ |
| insert | $O(1)$ |
| min | $O(n)$ |
| removeMin | $O(n)$ |
Priority Queue ADT $\rightarrow$ Sorted List Implementation
- We use a PositionalList which in turn uses DLL but sorted by nondecreasing keys.
- min or removeMin requires the retrieval or removal of the first element in $O(1)$ time.
- insert method inserts a key-value entry at the appropriate position after scanning the list in $O(n)$ time.
| Method | Sorted list |
|---|---|
| size | $O(1)$ |
| isEmpty | $O(1)$ |
| insert | $O(n)$ |
| min | $O(1)$ |
| removeMin | $O(1)$ |
Heap
- Unsorted list has excellent insert time but worse removeMin time.
Sorted list has excellent removeMin time but worse insert time. - Is it possible to get the best of both the worlds?
No! It is impossible to construct a data structure that has $O(1)$ for both insert and removeMin. Why? - We can definitely get the better of both the worlds using the heap data structure.
- Heap is the tree-based data structure for implementing the priority queue ADT.
| Method | Unsorted list | Sorted list | Heap |
|---|---|---|---|
| insert | $O(1)$ | $O(n)$ | $O(\log n)$ |
| removeMin | $O(n)$ | $O(1)$ | $O(\log n)$ |
java.util.PriorityQueue class
- User-defined priority can be given to the class by sending a comparator object when constructing the priority queue.
- Key-value pair can be considered by using java.util.AbstractMap.SimpleEntry class
| Our Priority Queue ADT | java.util.PriorityQueue class |
|---|---|
| insert(k,v) | add(new SimpleEntry(k,v)) |
| min() | peek() |
| removeMin() | remove() |
| size() | size() |
| isEmpty() | isEmpty() |
Example
Properties
A heap is a binary tree $T$ that satisfies two properties:
- Relational property. Deals with how keys are stored in $T$.
Heap-order property. Key stored at a node is less than or equal to the keys stored at its child nodes. - Structural property. Deals with the shape of $T$.
Complete binary tree property. A heap $T$ with maximum level $\ell$ is an almost-complete binary tree if levels $0,1,2,\ldots ,(\ell - 1)$ of $T$ have the maximal number of nodes possible (namely, level $i$ has $2i$ nodes, for $0 \le i \le \ell - 1$) and the remaining nodes at level $\ell$ reside in the leftmost possible positions at that level.
A heap $T$ storing $n$ entries has maximum level $\ell = \lfloor \log_2 n \rfloor$.
Operation $\rightarrow$ Insert
Insert$(k, v)$
- Insert pair $(k, v)$ at the last node
- Up-heap bubble until heap-order property is not violated
Operation $\rightarrow$ RemoveMin
RemoveMin$(k, v)$
- Remove the root node
- Move the last node to the root node position
- Down-heap bubble until heap-order property is not violated
Priority Queue ADT $\rightarrow$ Array-Based Heap Implementation
Array representation
Let $p$ be a node. Then the index $f(p)$ can be computed as follows. \[ f(p) = \left. \begin{cases} 0 & \text{ if $p$ is the root},\\ 2f(q) + 1 & \text{ if $p$ is the left child of position $q$},\\ 2f(q) + 2 & \text{ if $p$ is the right child of position $q$}. \end{cases} \right\} \]
Array implementation
import java.util.ArrayList;
import java.util.Comparator;
public interface Entry {
/**
* Returns the key stored in this entry.
* @return the entry's key
*/
K getKey();
/**
* Returns the value stored in this entry.
* @return the entry's value
*/
V getValue();
}
public interface PriorityQueue {
/**
* Returns the number of items in the priority queue.
* @return number of items
*/
int size();
/**
* Tests whether the priority queue is empty.
* @return true if the priority queue is empty, false otherwise
*/
boolean isEmpty();
/**
* Inserts a key-value pair and returns the entry created.
* @param key the key of the new entry
* @param value the associated value of the new entry
* @return the entry storing the new key-value pair
* @throws IllegalArgumentException if the key is unacceptable for this queue
*/
Entry insert(K key, V value) throws IllegalArgumentException;
/**
* Returns (but does not remove) an entry with minimal key.
* @return entry having a minimal key (or null if empty)
*/
Entry min();
/**
* Removes and returns an entry with minimal key.
* @return the removed entry (or null if empty)
*/
Entry removeMin();
}
public abstract class AbstractPriorityQueue implements PriorityQueue {
//---------------- nested PQEntry class ----------------
/**
* A concrete implementation of the Entry interface to be used within
* a PriorityQueue implementation.
*/
protected static class PQEntry implements Entry {
private K k; // key
private V v; // value
public PQEntry(K key, V value) {
k = key;
v = value;
}
// methods of the Entry interface
public K getKey() { return k; }
public V getValue() { return v; }
// utilities not exposed as part of the Entry interface
protected void setKey(K key) { k = key; }
protected void setValue(V value) { v = value; }
} //----------- end of nested PQEntry class -----------
// instance variable for an AbstractPriorityQueue
/** The comparator defining the ordering of keys in the priority queue. */
private Comparator comp;
/**
* Creates an empty priority queue using the given comparator to order keys.
* @param c comparator defining the order of keys in the priority queue
*/
protected AbstractPriorityQueue(Comparator c) { comp = c; }
/** Creates an empty priority queue based on the natural ordering of its keys. */
protected AbstractPriorityQueue() { this(new DefaultComparator()); }
/** Method for comparing two entries according to key */
protected int compare(Entry a, Entry b) {
return comp.compare(a.getKey(), b.getKey());
}
/** Determines whether a key is valid. */
protected boolean checkKey(K key) throws IllegalArgumentException {
try {
return (comp.compare(key,key) == 0); // see if key can be compared to itself
} catch (ClassCastException e) {
throw new IllegalArgumentException("Incompatible key");
}
}
/**
* Tests whether the priority queue is empty.
* @return true if the priority queue is empty, false otherwise
*/
@Override
public boolean isEmpty() { return size() == 0; }
}
public class HeapPriorityQueue extends AbstractPriorityQueue {
/** primary collection of priority queue entries */
protected ArrayList> heap = new ArrayList<>();
/** Creates an empty priority queue based on the natural ordering of its keys. */
public HeapPriorityQueue() { super(); }
/**
* Creates an empty priority queue using the given comparator to order keys.
* @param comp comparator defining the order of keys in the priority queue
*/
public HeapPriorityQueue(Comparator comp) { super(comp); }
/**
* Creates a priority queue initialized with the respective
* key-value pairs. The two arrays given will be paired
* element-by-element. They are presumed to have the same
* length. (If not, entries will be created only up to the length of
* the shorter of the arrays)
* @param keys an array of the initial keys for the priority queue
* @param values an array of the initial values for the priority queue
*/
public HeapPriorityQueue(K[] keys, V[] values) {
super();
for (int j=0; j < Math.min(keys.length, values.length); j++)
heap.add(new PQEntry<>(keys[j], values[j]));
heapify();
}
// protected utilities
protected int parent(int j) { return (j-1) / 2; } // truncating division
protected int left(int j) { return 2*j + 1; }
protected int right(int j) { return 2*j + 2; }
protected boolean hasLeft(int j) { return left(j) < heap.size(); }
protected boolean hasRight(int j) { return right(j) < heap.size(); }
/** Exchanges the entries at indices i and j of the array list. */
protected void swap(int i, int j) {
Entry temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
/** Moves the entry at index j higher, if necessary, to restore the heap property. */
protected void upheap(int j) {
while (j > 0) { // continue until reaching root (or break statement)
int p = parent(j);
if (compare(heap.get(j), heap.get(p)) >= 0) break; // heap property verified
swap(j, p);
j = p; // continue from the parent's location
}
}
/** Moves the entry at index j lower, if necessary, to restore the heap property. */
protected void downheap(int j) {
while (hasLeft(j)) { // continue to bottom (or break statement)
int leftIndex = left(j);
int smallChildIndex = leftIndex; // although right may be smaller
if (hasRight(j)) {
int rightIndex = right(j);
if (compare(heap.get(leftIndex), heap.get(rightIndex)) > 0)
smallChildIndex = rightIndex; // right child is smaller
}
if (compare(heap.get(smallChildIndex), heap.get(j)) >= 0)
break; // heap property has been restored
swap(j, smallChildIndex);
j = smallChildIndex; // continue at position of the child
}
}
/** Performs a bottom-up construction of the heap in linear time. */
protected void heapify() {
int startIndex = parent(size()-1); // start at PARENT of last entry
for (int j=startIndex; j >= 0; j--) // loop until processing the root
downheap(j);
}
// public methods
/**
* Returns the number of items in the priority queue.
* @return number of items
*/
@Override
public int size() { return heap.size(); }
/**
* Returns (but does not remove) an entry with minimal key.
* @return entry having a minimal key (or null if empty)
*/
@Override
public Entry min() {
if (heap.isEmpty()) return null;
return heap.get(0);
}
/**
* Inserts a key-value pair and return the entry created.
* @param key the key of the new entry
* @param value the associated value of the new entry
* @return the entry storing the new key-value pair
* @throws IllegalArgumentException if the key is unacceptable for this queue
*/
@Override
public Entry insert(K key, V value) throws IllegalArgumentException {
checkKey(key); // auxiliary key-checking method (could throw exception)
Entry newest = new PQEntry<>(key, value);
heap.add(newest); // add to the end of the list
upheap(heap.size() - 1); // upheap newly added entry
return newest;
}
/**
* Removes and returns an entry with minimal key.
* @return the removed entry (or null if empty)
*/
@Override
public Entry removeMin() {
if (heap.isEmpty()) return null;
Entry answer = heap.get(0);
swap(0, heap.size() - 1); // put minimum item at the end
heap.remove(heap.size() - 1); // and remove it from the list;
downheap(0); // then fix new root
return answer;
}
/** Used for debugging purposes only */
private void sanityCheck() {
for (int j=0; j < heap.size(); j++) {
int left = left(j);
int right = right(j);
if (left < heap.size() && compare(heap.get(left), heap.get(j)) < 0)
System.out.println("Invalid left child relationship");
if (right < heap.size() && compare(heap.get(right), heap.get(j)) < 0)
System.out.println("Invalid right child relationship");
}
}
} Complexity
| Method | Array heap | Linked-tree heap |
|---|---|---|
| size, isEmpty, min | $O(1)$ | $O(1)$ |
| insert | $O(\log n)^*$ | $O(\log n)$ |
| removeMin | $O(\log n)^*$ | $O(\log n)$ |
* = amortized complexity
- Up-heap and down-heap bubbling take $O(\log n)$ time.
- Array runtimes are amortized due to array resizing.
Priority Queue Sort
Priority-Queue-Sort(sequence $S$, priority queue $P$)
- Insert the $n$ elements of $S$ into $P$
- RemoveMin the $n$ elements of $P$ into $S$
/** Sorts sequence S, using initially empty priority queue P. */
public static void pqSort(PositionalList S, PriorityQueue P) {
int n = S.size();
for (int j = 0; j < n; j++) {
E element = S.remove(S.first());
P.insert(element, null); // element is key; null value
}
for (int j = 0; j < n; j++) {
E element = P.removeMin().getKey();
S.addLast(element); // the smallest key in P is next placed in S
}
}
Selection Sort (Set $P =$ Unsorted List)
| Sequence S | Priority Queue P | ||
|---|---|---|---|
| Input | (7, 4, 8, 2, 5, 3, 9) | () | |
| insert | (a) | (4, 8, 2, 5, 3, 9) | (7) |
| (b) | (8, 2, 5, 3, 9) | (7, 4) | |
| $\vdots$ | $\vdots$ | $\vdots$ | |
| (g) | () | (7, 4, 8, 2, 5, 3, 9) | |
| removeMin | (a) | (2) | (7, 4, 8, 5, 3, 9) |
| (b) | (2, 3) | (7, 4, 8, 5, 9) | |
| (c) | (2, 3, 4) | (7, 8, 5, 9) | |
| (d) | (2, 3, 4, 5) | (7, 8, 9) | |
| (e) | (2, 3, 4, 5, 7) | (8, 9) | |
| (f) | (2, 3, 4, 5, 7, 8) | (9) | |
| (g) | (2, 3, 4, 5, 7, 8, 9) | () |
- Phase 1 time $= \sum_{i = 1}^{n} \Theta(1) = \Theta(n)$
- Phase 2 time $= \sum_{i = n}^{1} O(i) = O(n^2)$
- Total time $= O(n^2)$
Insertion Sort (Set $P =$ Sorted List)
| Sequence S | Priority Queue P | ||
|---|---|---|---|
| Input | (7, 4, 8, 2, 5, 3, 9) | () | |
| insert | (a) | (4, 8, 2, 5, 3, 9) | (7) |
| (b) | (8, 2, 5, 3, 9) | (4, 7) | |
| (c) | (2, 5, 3, 9) | (4, 7, 8) | |
| (d) | (5, 3, 9) | (2, 4, 7, 8) | |
| (e) | (3, 9) | (2, 4, 5, 7, 8) | |
| (f) | (9) | (2, 3, 4, 5, 7, 8) | |
| (g) | () | (2, 3, 4, 5, 7, 8, 9) | |
| removeMin | (a) | (2) | (3, 4, 5, 7, 8, 9) |
| (b) | (2, 3) | (4, 5, 7, 8, 9) | |
| $\vdots$ | $\vdots$ | $\vdots$ | |
| (g) | (2, 3, 4, 5, 7, 8, 9) | () |
- Phase 1 time $= \sum_{i = 1}^{n} O(i) = O(n^2)$
- Phase 2 time $= \sum_{i = n}^{1} \Theta(1) = \Theta(n)$
- Total time $= O(n^2)$
Heap Sort (Set $P =$ Heap)
| Sequence S | Priority Queue P | ||
|---|---|---|---|
| Input | (7, 4, 8, 2, 5, 3, 9) | () | |
| insert | (a) | (4, 8, 2, 5, 3, 9) | (7) |
| (b) | (8, 2, 5, 3, 9) | (4, 7) | |
| $\vdots$ | $\vdots$ | $\vdots$ | |
| (g) | () | (2, 4, 3, 7, 5, 8, 9) | |
| removeMin | (a) | (2) | (3, 4, 8, 7, 5, 9) |
| (b) | (2, 3) | (4, 5, 8, 7, 9) | |
| (c) | (2, 3, 4) | (5, 7, 8, 9) | |
| (d) | (2, 3, 4, 5) | (7, 9, 8) | |
| (e) | (2, 3, 4, 5, 7) | (8, 9) | |
| (f) | (2, 3, 4, 5, 7, 8) | (9) | |
| (g) | (2, 3, 4, 5, 7, 8, 9) | () |
- Phase 1 time $= \sum_{i = 1}^{n} O(\log n) = O(n \log n)$
- Phase 2 time $= \sum_{i = n}^{1} O(\log n) = O(n \log n)$
- Total time $= O(n \log n)$
Complexity
| Sorting algorithm | Running time |
|---|---|
| Selection sort | $O(n^2)$ |
| Insertion sort | $O(n^2)$ |
| Heap sort | $O(n \log n)$ |