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

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