Priority Queues/Java

Two concrete priority queue classes and one abstract priority queue class implemented in Java. These classes can be found at git.charlesreid1.com.

You can also find the Java Collections implementation of the Priority Queue class here: http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/ff6c76f7733e/src/share/classes/java/util/PriorityQueue.java

Priority Queue Base Class

PriorityQueueBase class: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/PriorityQueueBase.java

This base class is an abstract class that defines a key-value item utility class, defines a few simple methods, and requires base classes to implement several other methods.

Sorted Priority Queue

SortedPriorityQueue class: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/SortedPriorityQueue.java

This class implements a sorted priority queue using an O(N) insertion sort for each add operation (start from the back, swap your way toward the front) and a built-in Java Collections API Linked List (a doubly-linked list).

Slow add, fast remove.

Unsorted Priority Queue

UnsortedPriorityQueue class: https://charlesreid1.com:3000/cs/java/src/master/priority-queues/UnsortedPriorityQueue.java

This class implements an unsorted priority queue that does not keep track of the minimum element and must perform an O(N) sequential search for each removal operation.

Fast add, slow remove.