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.