Priority Queues/Sorted

Git Code

Link on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/priority-queues/SortedPQ.java

Notes

See also Priority Queues for notes on the general data structure.

Sorted priority queue class implements a sorted list to keep track of items in the priority queue.

This class implements insertion sort for each add operation to keep the minimum at the front of the list.

Big O Cost

Because the list is kept sorted, the add() method is an O(N) operation.

If we have a linked list we can implement this as an insertion sort (that is, walk through the list from the back and look for the proper place to insert the new item).

if we have an array list and therefore have random access to items, we can perform a binary search, which is only an O(log N) operation, but then we have to potentially shift N items down in the array to make room for the inserted item, for an O(N) cost overall.

The removal of the minimum item is then very easy - it is removed from the front of the list. Removal (and peek) is an O(1) operation.

Implementation

To implement a priority queue:

• Implement interface to require priority queue objects (to provide basic functions) and priority queue item objects (key-value pairs)
• Implement abstract class for priority queues (very basic functionality only - constructor definition and key validation method)
• Implement concrete class that actually uses a container to maintain a sorted list (contains most of the implementation details)

To implement a sorted priority queue:

Grand Strategy

The grand strategy to implement this type of data structure is laid out above:

• Start with interfaces - following Priority_Queues/ADT
• Define abstract data type - following Priority_Queues/ADT
• Define concrete class

Let's walk through each step:

• Start with interfaces at the highest and most abstract level, defining basic functionality. These will help define the problem, how you are solving it, and how your algorithm will work. This helps you write tests. This also creates your public interface and helps decide what should be public and what should be private.
• Move on to the abstract data type. This should not contain much content, but anything basic - like constructors/initialization or private fields - that are independent of implementation.
• Spend most of your time on the concrete class.

Interface

The priority queue interface is a templated/generic type class. It defines the basic methods - we should be able to add and remove items, as well as query the state of the queue. These are enabled through an insert method, a peek minimum method, and a remove minimum method.

Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/PriorityQueue.java

PriorityQueue.java

import java.util.Iterator;

/** Define some exceptions.  */
class Illegal extends IllegalArgumentException {}
class Empty extends IndexOutOfBoundsException {}

/** Priority Queue interface.
 *
 * This defines the two simplest methods a priority queue can get away with.
 *
 * This is essentially a barebones list of methods. 
 *
 * Note that Item<K,V> is not defined here, it is defined in your concrete implementation.
 */
public interface PriorityQueue<K,V> extends Iterable<K> {
		//extends Iterable<K> { 

	/** Returns true if the priority queue was changed. */
	public void insert(K k, V v);

	/** Remove and return the minimum element in this queue. */
	public V removeMin() throws Empty;

	/** Return, but do not remove, the minimum element in this queue. */
	public V peekMin() throws Empty;

	/** Returns a key-based iterator. */
	public Iterator<K> iterator();

	/** Returns an iterable container with all of the Items in this queue. */
	protected Iterable<Item<K,V>> items();

	/** Returns the number of elements in this queue. */
	public int size();

	/** Returns true if there are no elements in this queue. */
	public boolean isEmpty();

	/** Returns a string representation of this priority queue. */
	public String toString();
}

Priority Queue Abstract Data Type

The parent type is a priority queue abstract data type. The class does not do a lot of work, but it does establish the technique the Priority Queue will use to sort Items - and it defines the Item class, representing nodes of data in the list.

Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/AbstractPriorityQueue.java

Runthrough:

• Front matter
• The first thing the abstract class does is define the key-value item object. This is protected because it is for internal use only - the intent here is to define a priority queue where the priority is associated with the value, but not bundled with the value.
• Following the protected class that wraps key-value pairs, the actual content of the abstract class reveals the strategy that the priority queue uses for keeping items sorted.
• The abstract priority queue has a private Comparator<K> field called keyCompare. This Comparator object can be very simple, and need only expose a compare(a,b) method. See Comparators vs Comparable. When the constructor is called, the default constructor simply defines a new default comparator. Alternatively, a Comparator object can be passed in and used to compare keys. This allows different priority queue objects to be created, each with their own way of comparing key objects.
• A compare() method to compare two items in a list using a Comparator object rather than the Item objects' natural ordering is also implemented.

import java.util.Comparator;

/** Priority Queue ADT.
 *
 * Model elements and their priorities as a key-value composite Entry.
 *
 * The ADT is where we define any constructors or methods
 * that are possible to define without knowing the concrete
 * implementation of our priority queue.
 */
public abstract class AbstractPriorityQueue<K,V> 
			implements PriorityQueue<K,V> {

	protected static class Item<K,V> {
		private K k;
		private V v;
		public Item(K key, V value) { 
			this.k = key; this.v = value;
		}

		/** Return the key associated with this element. */
		public K getKey() { return k; }

		/** Return the value associated with this element. */
		public V getValue() { return v; }

		/** Set the key associated with this element. */
		protected void setKey(K k) { this.k = k; }

		/** Set the value associated with this element. */
		protected void setValue(V v) { this.v = v; }

		public String toString() { return "("+v+")"; }
	}

	// Key comparator
	private Comparator<K> keyCompare;

	/** Create an empty priority queue that will use the given comparator to sort the item keys. */
	protected AbstractPriorityQueue(Comparator<K> c) { keyCompare = c; }

	/** Create an empty priority queue with a default comparator */
	protected AbstractPriorityQueue() { 
		// this() call must be first thing to happen in constructor
		this( new DefaultComparator<K>() );
	}

	/** Define a way to compare two Items.
	 * This is a more general way than defiing a compareTo method.
	 * By using a Comparator object and defining the compare(a,b) method,
	 * we can create multiple priority queues, each using their own
	 * method for sorting keys.
	 *
	 * Throws an unchecked WeirdKey.
	 * */
	protected int compare(Item<K,V> a, Item<K,V> b) { 
		// Compare two Items 
		// using keyComparator
		// and passing their keys.
		// Don't bother with the details.
		return keyCompare.compare(a.getKey(), b.getKey());
	}

	/** Determine whether a key can be compared to itself using our comparator object. */
	protected boolean checkKey(K key) {
		try{ 
			return keyCompare.compare(key,key)==0;
		} catch (ClassCastException e) {
			throw new WeirdKey();
		}
	}

	/** Test whether priority queue is empty - assumes size() method is implemented. */
	public boolean isEmpty() {
		return (size()==0);
	}

}

Sorted Priority Queue Class

The entirety of the Sorted Priority Queue class.

Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/SortedPQ.java

import java.util.LinkedList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

// unsorted priority queue
public class SortedPQ<K,V> 
	extends AbstractPriorityQueue<K,V> 
	implements Iterable<K> { 
	
	// primary collection
	private LinkedList<Item<K,V>> data; 

	// constructor calls the super
	public SortedPQ() { 
		super(); 
		data = new LinkedList<>();
	}
	public SortedPQ(Comparator<K> c) { 
		super(c); 
		data = new LinkedList<Item<K,V>>();
	}

	public void insert(K key, V value) { 
		checkKey(key);

		Item<K,V> newest = new Item<K,V>(key,value);

		if(isEmpty()) { 
			data.addFirst(newest);
		} else {
			
			Iterator<Item<K,V>> iter = data.descendingIterator();
			Item<K,V> walker = iter.next();
			// keep moving left while newest is less than walker
			int ix = data.size();
			while(walker!=null && compare(newest, walker)<0 ) {
				// advance walker left (left = next, descending iterator)
				try {
				    walker = iter.next();
					ix--;
				} catch(NoSuchElementException e) { 
					walker = null;
				}
			}
			// check what caused the stop
			if(walker==null) {  
				data.addFirst(newest);
			} else {
				data.add(ix,newest);
			}
		}
	}

	public V peekMin() {
		return data.get(0).getValue();
	}

	public V removeMin() {
		Item<K,V> it = data.remove(0);
		return it.getValue();
	}

	public int size() { 
		return data.size();
	}

	public String toString() { 
		return data.toString();
	}

	protected Iterable<Item<K,V>> items() { 
		return data;
	}

	protected class ItemIterator implements Iterator<K> {
		Iterator<Item<K,V>> it;
		public ItemIterator() { 
			it = items().iterator();
		}
		public boolean hasNext() { return it.hasNext(); }
		public K next() { return it.next().getKey(); }
		public void remove() { it.remove(); }
	}

	public Iterator<K> iterator() { 
		return new ItemIterator();
	}

}

Making it iterable

To make the sorted priority queue class iterable, we can have two things to do:

• Populate our items/data in a data container that is iterable (already done, since we are using Linked List), and
• Define a key (or value) iterator class. This is a simple wrapper class around the built in linked list iterator.

Here, we accomplish the first task:

	protected Iterable<Item<K,V>> items() { 
		return data;
	}

and here we accomplish the second:

	protected class ItemIterator implements Iterator<K> {
		Iterator<Item<K,V>> it;
		public ItemIterator() { 
			it = items().iterator();
		}
		public boolean hasNext() { return it.hasNext(); }
		public K next() { return it.next().getKey(); }
		public void remove() { it.remove(); }
	}

	public Iterator<K> iterator() { 
		return new ItemIterator();
	}

Insert Method - More Detail

Let's run through that insert method one more time in greater detail.

	public void insert(K key, V value) { 
		checkKey(key);

Start by checking that the key object is a comparable item, and that a compareTo method has been implemented for it.

Next, check for the empty case.

		Item<K,V> newest = new Item<K,V>(key,value);

		if(isEmpty()) { 
			data.addFirst(newest);
		} else {

At this point, we have the Item we are trying to insert into the list, in a variable called newest. We want to iterate through the list to find the new location to insert the Item. This class uses a built-in LinkedList so we utilize an integer index and the built-in methods of the list to add the item at that location.

Starting with a descending iterator through the list, we work our way from the back to the front. We already checked for an empty priority queue, so we know there must be at least one item in the container. This allows us to do a fencepost algorithm/pattern, where we examine one item in the list of items (data), then run a while loop.

			Iterator<Item<K,V>> iter = data.descendingIterator();
			Item<K,V> walker = iter.next();
			// keep moving left while newest is less than walker
			int ix = data.size();
			while(walker!=null && compare(newest, walker)<0 ) {
				// advance walker left (left = next, descending iterator)
				try {
					walker = iter.next();
					ix--;
				} catch(NoSuchElementException e) { 
					walker = null;
				}
			}
			// check what caused the stop
			if(walker==null) {  
				data.addFirst(newest);
			} else {
				data.add(ix,newest);
			}
		}
	}

Let's examine the case of a one-item list.

If there is only one item in the list, we run the while loop one or zero times, depending on the results of the comparison between newest and walker (the last item our iterator removed from the list).

• If newest is greater than walker, we can add newest to the end of the list. We skip the while loop, and add at index 1 (the value of ix).
• If newest is less than walker, we need to run through the loop once, advance the iterator back one, and update the insertion index. This will then insert the walker at the beginning of the list. The next time through the while loop, the test returns false because walker is null (we ran next() on an iterator pointing to the beginning of the list).
• The walker variable is not null, so we add at the front.

If two items in the list, we might end up running while loop no times (largest item in list), in which case ix = 2, inserting at end of list. We might end up running while loop one time (median of list), in which case ix = 1, and we insert in the middle. Or we might run the while loop twice, ix = 0, and we insert at the beginning. Only in the last case does the walker pointer become null and we execute the data.addFirst method.