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.

Code

Link: https://charlesreid1.com:3000/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

/** 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 PQEntry<K,V> implements Entry<K,V> {
		private K k;
		private V v;
		public PQEntry(K key, V value) { 
			this.k = key; this.v = value;
		}

		/* Methods associated with the Entry interface: */

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

		/* Protected utility methods to modify the values (get/set): */ 

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

	}

}