A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like “a list” or “a map”; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
My motivation for this blog is section 2.4 Priority Queues in the book Algorithms fourth edition by Robert Sedgewick and Kevin Wayne. After becoming at ease with queues and heaps the book presents an implementation of maximum heap priority queue. The original source code may be found in the website for the book at http://algs4.cs.princeton.edu/home/
A priority queue has two main operations: [1] remove the maximum and [2] insert. These two operations are frequently found in operations at different levels. I have encountered the need for priority queues in several programs and modules. If you are interested in how both operations may be conducted on an array, I invite you to get a copy of the book and experiment with priority queues. In this blog I will use modified code from the book with special attention to the swim() and sink() methods.
Let’s first take a look at console output from the Eclipse IDE:
A
E
G
H
I
N
O
P
R
S
T
–
–
–
–
–
–
–
–
–
–
–
*
1 2 3 4 5 6 7 8 9 10
show <<< pq:
main <<< insert ==>A<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: A
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: A
main <<< insert ==>E<==
resize <<< capacity: 4
1 2 3 4 5 6 7 8 9 10
show <<< pq: E A
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: E A
main <<< insert ==>G<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: G A E
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: G A E
main <<< insert ==>H<==
resize <<< capacity: 8
1 2 3 4 5 6 7 8 9 10
show <<< pq: H G E A
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: H G E A
main <<< insert ==>I<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: I H E A G
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: I H E A G
main <<< insert ==>N<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: N H I A G E
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: N H I A G E
main <<< insert ==>O<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: O H N A G E I
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: O H N A G E I
main <<< insert ==>P<==
resize <<< capacity: 16
1 2 3 4 5 6 7 8 9 10
show <<< pq: P O N H G E I A
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: P O N H G E I A
main <<< insert ==>R<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: R P N O G E I A H
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: R P N O G E I A H
main <<< insert ==>S<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: S R N O P E I A H G
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: S R N O P E I A H G
main <<< insert ==>T<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: T S N O R E I A H G P
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: T S N O R E I A H G P
main <<< pq.delMax ==>T<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: S R N O P E I A H G
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: S R N O P E I A H G
main <<< pq.delMax ==>S<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: R P N O G E I A H
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: R P N O G E I A H
main <<< pq.delMax ==>R<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: P O N H G E I A
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: P O N H G E I A
main <<< pq.delMax ==>P<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: O H N A G E I
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: O H N A G E I
main <<< pq.delMax ==>O<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: N H I A G E
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: N H I A G E
main <<< pq.delMax ==>N<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: I H E A G
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: I H E A G
main <<< pq.delMax ==>I<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: H G E A
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: H G E A
resize <<< capacity: 8
main <<< pq.delMax ==>H<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: G A E
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: G A E
main <<< pq.delMax ==>G<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: E A
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: E A
resize <<< capacity: 4
main <<< pq.delMax ==>E<==
1 2 3 4 5 6 7 8 9 10
show <<< pq: A
**** **** ****
1 2 3 4 5 6 7 8 9 10
show <<< pq: A
main <<< pq.delMax ==>A<==
1 2 3 4 5 6 7 8 9 10
show <<< pq:
**** **** ****
main <<< pq.size: 0
The output was produced by the following Java code:
/**
* Unit tests the {@code MaxPQ} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
MaxPQ<String> pq = new MaxPQ<String>();
// **** ****
while (true) {
String item = StdIn.readString();
// **** check if we are done ****
if (item.equals(“*”)) {
break;
}
// **** ****
pq.show();
// **** insert new item ****
if (!item.equals(“-“)) {
System.out.println(“main <<< insert ==>” + item + “<==”);
pq.insert(item);
}
// **** delete max item ****
else if (!pq.isEmpty()) {
System.out.println(“main <<< pq.delMax ==>” + pq.delMax() + “<==”);
}
// **** ****
pq.show();
System.out.println(“**** **** ****”);
}
// **** ****
StdOut.println(“main <<< pq.size: ” + pq.size());
}
To start a priority queue (pq) is instantiated. A loop reads input until done (‘*’). When the ‘-‘ character is encountered, the maximum value in the priority queue is removed. When any other character is encountered, the character is inserted into the priority queue. At the start and end of the loop the array used to implement the priority queue is displayed. This allows us to observe how the elements in the array are updated in order to maintain the maximum priority element at the root (element 1 in the array) and allow with not much effort insertions of new elements.
The following diagram provides a tree view of the contents of the pq array in this example:
As one can see, the child nodes for any node always contain elements with values less than the parent. For example, node R has children with values G and P (both less than R). The root of the tree contains value T which is larger than the children (S and N).
Also, given a node, k (e.g., 5) the two children are at locations k * 2 (e.g., 10) and (k * 2) + 1 (e.g., 11). Using this organization (the first element in the array 0 is not used) the two key operations implemented by methods swim() and sink() can be implemented with very few lines of code.
Following is the Java code for swim() method:
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
exch(k, k/2);
k = k / 2;
}
}
Following is the Java code for the sink() method:
private void sink(int k) {
while (2 * k <= n) {
int j = 2 * k;
if ((j < n) && less(j, j + 1)) {
j++;
}
if (!less(k, j)) {
break;
}
exch(k, j);
k = j;
}
}
When an element is inserted it invokes the insert() method whose Java code follows:
public void insert(Key x) {
// **** double size of array if necessary ****
if (n >= pq.length – 1) {
resize(2 * pq.length);
}
// **** add x, and percolate it up to maintain heap invariant ****
pq[++n] = x;
swim(n);
assert isMaxHeap();
}
The code that implements an insertion places the key in the next available entry in the array while incrementing the count of elements by one. The newly inserted element swims up to the proper location making used of the swim() method.
For example, if we take a look at the following screen capture:
1 2 3 4 5 6 7 8 9 10
show <<< pq: O H N A G E I <== BEFORE inserting P
main <<< insert ==>P<==
resize <<< capacity: 16
1 2 3 4 5 6 7 8 9 10
show <<< pq: P O N H G E I A <== AFTER inserting P
As you can see, the P element went up to the root of the tree (first element in the pq array).
Following is the complete modified Java code. If you are interested in the original code you will find it on the web site for the Algorithms book:
package edu.princeton.cs.algs4;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MaxPQ<Key> implements Iterable<Key> {
private Key[] pq; // store items at indices 1 to n
private int n; // number of items on priority queue
private Comparator<Key> comparator; // optional Comparator
/**
* Initializes an empty priority queue with the given initial capacity.
*
* @param initCapacity the initial capacity of this priority queue
*/
public MaxPQ(int initCapacity) {
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
}
/**
* Initializes an empty priority queue.
*/
public MaxPQ() {
this(1);
}
/**
* Initializes an empty priority queue with the given initial capacity,
* using the given comparator.
*
* @param initCapacity the initial capacity of this priority queue
* @param comparator the order in which to compare the keys
*/
public MaxPQ(int initCapacity, Comparator<Key> comparator) {
this.comparator = comparator;
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
}
/**
* Initializes an empty priority queue using the given comparator.
*
* @param comparator the order in which to compare the keys
*/
public MaxPQ(Comparator<Key> comparator) {
this(1, comparator);
}
/**
* Initializes a priority queue from the array of keys.
* Takes time proportional to the number of keys, using sink-based heap construction.
*
* @param keys the array of keys
*/
public MaxPQ(Key[] keys) {
n = keys.length;
pq = (Key[]) new Object[keys.length + 1];
for (int i = 0; i < n; i++) {
pq[i+1] = keys[i];
}
for (int k = n/2; k >= 1; k–) {
sink(k);
}
assert isMaxHeap();
}
/**
* Returns true if this priority queue is empty.
*
* @return {@code true} if this priority queue is empty;
* {@code false} otherwise
*/
public boolean isEmpty() {
return n == 0;
}
/**
* Returns the number of keys on this priority queue.
*
* @return the number of keys on this priority queue
*/
public int size() {
return n;
}
/**
* Returns a largest key on this priority queue.
*
* @return a largest key on this priority queue
* @throws NoSuchElementException if this priority queue is empty
*/
public Key max() {
if (isEmpty()) throw new NoSuchElementException(“Priority queue underflow”);
return pq[1];
}
/*
* helper function to double the size of the heap array
*/
private void resize(int capacity) {
System.out.println(“resize <<< capacity: ” + capacity);
assert capacity > n;
Key[] temp = (Key[]) new Object[capacity];
for (int i = 1; i <= n; i++) {
temp[i] = pq[i];
}
pq = temp;
}
/*
* helper function that displays the contents of the array of keys
*/
public void show() {
System.out.print(” “);
for (int i = 1; i <= 10; i++) {
System.out.print(i + ” “);
}
System.out.println();
System.out.print(“show <<< pq: “);
for (Key k : pq) {
if (k != null) {
System.out.print(k + ” “);
}
}
System.out.println();
}
/**
* Adds a new key to this priority queue.
*
* @param x the new key to add to this priority queue
*/
public void insert(Key x) {
// **** double size of array if necessary ****
if (n >= pq.length – 1) {
resize(2 * pq.length);
}
// **** add x, and percolate it up to maintain heap invariant ****
pq[++n] = x;
swim(n);
assert isMaxHeap();
}
/**
* Removes and returns a largest key on this priority queue.
*
* @return a largest key on this priority queue
* @throws NoSuchElementException if this priority queue is empty
*/
public Key delMax() {
if (isEmpty()) {
throw new NoSuchElementException(“Priority queue underflow”);
}
Key max = pq[1];
exch(1, n–);
sink(1);
pq[n+1] = null; // to avoid loiterig and help with garbage collection
if ((n > 0) && (n == (pq.length – 1) / 4)) {
resize(pq.length / 2);
}
assert isMaxHeap();
return max;
}
/***************************************************************************
* Helper functions to restore the heap invariant.
***************************************************************************/
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
exch(k, k/2);
k = k / 2;
}
}
private void sink(int k) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && less(j, j + 1)) {
j++;
}
if (!less(k, j)) {
break;
}
exch(k, j);
k = j;
}
// show();
}
/***************************************************************************
* Helper functions for compares and swaps.
***************************************************************************/
private boolean less(int i, int j) {
if (comparator == null) {
return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
}
else {
return comparator.compare(pq[i], pq[j]) < 0;
}
}
private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}
// is pq[1..N] a max heap?
private boolean isMaxHeap() {
return isMaxHeap(1);
}
// is subtree of pq[1..n] rooted at k a max heap?
private boolean isMaxHeap(int k) {
if (k > n) return true;
int left = 2 * k;
int right = 2 * k + 1;
if (left <= n && less(k, left)) return false;
if (right <= n && less(k, right)) return false;
return isMaxHeap(left) && isMaxHeap(right);
}
/***************************************************************************
* Iterator.
***************************************************************************/
/**
* Returns an iterator that iterates over the keys on this priority queue
* in descending order.
* The iterator doesn’t implement {@code remove()} since it’s optional.
*
* @return an iterator that iterates over the keys in descending order
*/
public Iterator<Key> iterator() {
return new HeapIterator();
}
private class HeapIterator implements Iterator<Key> {
// create a new pq
private MaxPQ<Key> copy;
// add all items to copy of heap
// takes linear time since already in heap order so no keys move
public HeapIterator() {
if (comparator == null) copy = new MaxPQ<Key>(size());
else copy = new MaxPQ<Key>(size(), comparator);
for (int i = 1; i <= n; i++)
copy.insert(pq[i]);
}
public boolean hasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }
public Key next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return copy.delMax();
}
}
/**
* Unit tests the {@code MaxPQ} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
MaxPQ<String> pq = new MaxPQ<String>();
// **** ****
while (true) {
String item = StdIn.readString();
// **** check if we are done ****
if (item.equals(“*”)) {
break;
}
// **** ****
pq.show();
// **** insert new item ****
if (!item.equals(“-“)) {
System.out.println(“main <<< insert ==>” + item + “<==”);
pq.insert(item);
}
// **** delete max item ****
else if (!pq.isEmpty()) {
System.out.println(“main <<< pq.delMax ==>” + pq.delMax() + “<==”);
}
// **** ****
pq.show();
System.out.println(“**** **** ****”);
}
// **** ****
StdOut.println(“main <<< pq.size: ” + pq.size());
}
}
So the next time that you blindly choose a priority queue from the Java library you will be able to better understand and appreciate a possible implementation for a maximum priority queue using a heap.
If you have comments or questions regarding this blog post or any other post in this blog, please do not hesitate and send me a message. I will keep your name in confidence unless you explicitly allow me to use it.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa