Priority Queues/Sorted

Git Code

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

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

Again, this class doesn't do much - most of the work is done in the concrete class.

It can implement a basic constructor, though.

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

	}
}

asdfasdfasdfasdf

The class was organized as follows:

• Class extended priority queue base class PriorityQueueBase<T>
• Class accepted generic types <T> (in retrospect, this should have been <K,V>)
• Class utilizes a protected Item<T> class in the base class for handling key-value pairs
• Class stores key-value items in a linked list of Item<T> objects

Utility methods:

• toString
• isEmpty
• size

Functional methods:

• add - the add method needs to search for a location to put a new element, to prevent the list from getting out of order. This is an O(N) operation.
• removeMin - this is an O(1) operation, remove from the front of the list.
• peekMin - return the min without removing it

Front matter and constructor

import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.Random;

class Empty extends IllegalStateException {}

public class SortedPriorityQueue<T> extends PriorityQueueBase<T> { 

	// Sorted list of items in our priority queue
	LinkedList<Item<T>> data; 

	/** Constructor of sorted priority queue initializes list of key-value items. */
	public SortedPriorityQueue() { 
		super(); 
		// Initialize the array of items
		data = new LinkedList<Item<T>>();
	}

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();
	}