Priority Queues/Sorted

Git Code

Link on git.charlesreid1.com: https://charlesreid1.com:3000/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://charlesreid1.com:3000/cs/java/src/master/priority-queues/PriorityQueue.java

PriorityQueue.java

/** 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> { 

	/** Returns true if the priority queue was changed. */
	public boolean insert(k,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. */
	public 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 isEmpty();
}

Abstract 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://charlesreid1.com:3000/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;

/** Define a weird key exception.
 * This gets raised when a key cannot be compared to itself. 
 * This extends IllegalArgumentException which means it is unchecked. */
class WeirdKey extends IllegalArgumentException {};

/** 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);
	}
}

ASDF

not updated to this point.

Utility methods

	/** Return string representation of the items. */
	public String toString() { return data.toString(); }

	/** Get number of elements in the queue. */
	public int size() { return this.size; }

	/** Return true if there are no elements in this queue. */ 
	public boolean isEmpty() { return this.size()==0; }

Add method

	public void add(int k, T v) { 

		Item<T> newest = new Item<T>(k,v);
		ListIterator<Item<T>> iter = data.listIterator(data.size());

		// Deal with the empty list case
		if(!iter.hasPrevious()) { 
			data.addFirst(newest);
		} else {

			Item<T> walk = iter.previous();
			int size = data.size();
			// inner check
			while(iter.hasPrevious() && newest.compareTo(walk) < 0) { 
				walk = iter.previous();
				size--;
			}

			// Reached the end - check which condition it was
			if(!iter.hasPrevious()) {
				// Iterator is emptied out
				// Add to front
				// Highest priority
				data.addFirst(newest);
			} else {
				// Add at hurrr
				iter.add(newest);
			}
		}

		// Finally, always increment
		this.size++;
	}

RemoveMin and PeekMin

	/** Remove the minimum item to the sorted priority queue.
	 *
	 * The priority queue is maintained in sorted order so this is an O(1) operation.
	 */
	public T peekMin() throws Empty { 
		if(isEmpty()) { 
			throw new Empty();
		}
		Item<T> top = data.getFirst();
		return top.getValue();
	}

	public T removeMin() throws Empty { 
		if(isEmpty()) { 
			throw new Empty();
		}
		Item<T> top = data.removeFirst();
		this.size--;
		return top.getValue();
	}