Priority Queues/Sorted

Git Code

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

Notes

Main article: Priority Queues

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.

This means add() is O(N).

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.

Class

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