Priority Queues/ADT

Notes

Background on what a priority queue is: Priority Queues

Background on what abstract data types are: Abstract Data Types

The priority queues abstract data type can be implemented with two components: an interface, and an abstract class.

The first component is an interface, which is an "inheritance-lite" way of specifying methods that a priority queue must implement, but without providing or specifying any further details. This can be thought of as a purely abstract class - there is absolutely nothing concrete that can be defined in the interface. (See also: Java/Interfaces).

The second component is an abstract class, which is slightly more "heavyweight" than an interface. This is a place where you can specify actual implementation details about the class, so long as they do not depend on the concrete implementation details (e.g., whether the underlying data is stored in an array or a list).

Both of them use generic types for the key and value types, K V.

See code below for more information.

Java Code

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

Priority queue interface

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

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

	}

	// 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() { 
		DefaultComparator<K> boring = new DefaultComparator<K>();
		this(boring);
	}

	/** 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 is valid. */
	protected boolean checkKey(K key) {
		try{ 
			return keyComparator.compare(key,key)==0;
		} catch (ClassCastException e) {
			throw new WeirdKey("Nope");
		}
	}

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

}