Huffman coding; what's next
Table of contents
Priority queues
Suppose we want to manage a waiting list of hospital patients. We’d like to add new patients to the waiting list and remove the patient who should be served next as efficiently as possible. A LinkedList-based Queue solves this problem in constant time for both add and remove.
However, in real life, we want to prioritize patients who need the most urgent help. A regular Queue serves patients in a first-in, first-out (FIFO) manner. Someone with a mild condition would be seen before someone with a life-threatening condition just because they showed up first. Instead, we’d like to design a PriorityQueue: a collection that optimizes for returning the highest priority element.
Describe how to implement a priority queue with an unordered linked list.
In an unordered linked list, we can put our items anywhere in the list. This will make insertion fast because we can add the item to the front of the list in constant time, but finding the maximum slow since we need to scan across the entire linked list.
Describe how to implement a priority queue with an ordered linked list.
In an ordered linked list, the opposite is true. We can find the maximum quickly since we can maintain a reference to it (either the front or back of the list, our choice), allowing us to remove and return the maximum priority item in constant time. However, this slows down the insertion process since we need to find the exact, ordered position for the item in the list.
Describe how to implement a priority queue with a binary search tree.
A binary search tree maintains the order of items in the structure of the tree. The smallest key is stored in the leftmost node in the tree while the largest key is stored in the rightmost node in the tree. Therefore, we can keep a reference to the rightmost node in the tree and maintain it as we add items and remove the maximum priority item from the priority queue.
However, binary search trees store only unique elements. In general, a priority queue should be able to store duplicates.
Java provides a PriorityQueue class that implements the Queue interface including the methods add, remove, peek, size, and isEmpty. The main difference is that the PriorityQueue class removes elements in sorted order, from lowest priority to highest priority.
Queue<Character> pq = new PriorityQueue<>();
pq.add('c');
pq.add('b');
pq.add('a');
while (!pq.isEmpty()) {
System.out.print(pq.remove());
}
The output of this code snippet is “abc” as defined by the compareTo method in the Character class. In order to use a priority queue with our own data types, we’ll need to implement the Comparable interface.
Note that, while the remove method will remove elements in sorted order, the PriorityQueue class does not store its elements in sorted order. Printing out the pq will result in the following output.
[a, c, b]
This is because the PriorityQueue promises that the elements will be removed in sorted order, but does not promise anything about how it actually stores it.