The PriorityQueue and LinkedList Classes – Collections: Part II
By Jaime Williams / June 23, 2021 / No Comments / Introduction to Streams, Oracle Certification Exam, The NavigableSet Interface
The PriorityQueue<E> and LinkedList<E> Classes
Both the PriorityQueue<E> and LinkedList<E> classes implement the Queue<E> interface. Unless bidirectional iteration is necessary, other queue implementations should be considered, and not the LinkedList<E> class. (The LinkedList<E> class is also eclipsed by the introduction of the ArrayDeque<E> class when it comes to implementing deques, as we will see shortly.)
As the name suggests, the PriorityQueue<E> class is the obvious implementation for a queue with priority ordering. The implementation is based on a priority heap, a tree-like structure that yields an element at the head of the queue according to the priority ordering, which is defined either by the natural ordering of its elements or by a comparator. In the case of several elements having the same priority, one of them is chosen arbitrarily.
Elements of a PriorityQueue<E> are not sorted. The queue only guarantees that elements can be removed in priority order, and any iteration using an iterator does not guarantee to abide by the priority order.
The PriorityQueue<E> class provides the following constructors:
PriorityQueue()
PriorityQueue(int initialCapacity)
The default constructor creates a new, empty PriorityQueue with default initial capacity and natural ordering. The second constructor creates a new, empty PriorityQueue with the specified initial capacity and natural ordering.
PriorityQueue(Comparator<? super E> comparator)
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
Both constructors create a new, empty PriorityQueue where the ordering is defined by the specified comparator. The priority queue created by the first and the second constructors has the default initial capacity and the specified initial capacity, respectively.
PriorityQueue(PriorityQueue<? extends E> pq)
PriorityQueue(SortedSet<? extends E> set)
PriorityQueue(Collection<? extends E> c)
The first and the second constructors create a new PriorityQueue with the ordering and the elements from the specified priority queue or sorted set, respectively.
The last constructor creates a new PriorityQueue containing the elements in the specified collection. It will have natural ordering of its elements, unless the specified collection is either a SortedSet<E> or another PriorityQueue, in which case, the collection’s ordering will be used.
Example 15.7 illustrates using priority queues. The example shows how priority queues maintain objects of the Task class. The natural ordering of the objects in this class is based on the task number (Integer). This natural ordering will result in the priority queue yielding its elements in ascending order of the task numbers—that is, tasks with smaller task numbers will have higher priority.
In Example 15.7, the main() method in the class TaskExecutor creates an array with some tasks at (1). The method essentially creates empty priority queues with different priority orderings, at (2) through (7), and calls the testPQ() method at (8) to execute tasks passed in the array using the supplied priority queue.
private static void testPQ(Task[] taskArray, PriorityQueue<Task> pq) { // (8)
…
}
The testPQ() method at (8) loads the queue at (9) from the array of tasks. It calls the offer() method to insert a task in the priority queue. The method then calls the peek() method at (10) to examine the task at the head of the queue. The tasks are executed by removing them one by one at (11) by calling the poll() method. The output shows the order in which the tasks are executed, depending on the priority ordering.
The priority queue pq1 at (2) has its priority ordering defined by the natural ordering of the tasks.
PriorityQueue<Task> pq1 = new PriorityQueue<>(); // (2)
Note that the text representation of the queue in the output
Queue before executing tasks: [100@breakfast, 200@lunch, 300@dinner, 200@tea]
does not reflect the tasks in priority order. It just shows what tasks are in the queue. The text representation of the queue is generated by the print method running an iterator over the queue. The iterator is under no obligation to take the priority order into consideration. The output also shows that the task with the highest priority (i.e., the smallest task number) is at the head of the queue:
Task at the head: 100@breakfast
The call to the poll() method in the while loop at (11) removes tasks in priority order, as verified by the output:
Doing tasks: 100@breakfast 200@tea 200@lunch 300@dinner
Since two of the tasks have the same priority, the queue selects which one should be chosen first. The queue is empty when the peek() method returns null.
The priority queue pq2 at (3) has its priority ordering defined by the reverse natural ordering returned by the static method reverseOrder() of the Comparator<E> interface:
PriorityQueue<Task> pq2 = new PriorityQueue<>(Comparator.reverseOrder());
Both priority queues pq3 and pq4 use reversed ordering based on the task name. This ordering is defined for pq3 and pq4 by a lambda expression at (4) and by methods of the Comparator<E> interface at (7), respectively. The latter implementation is obviously to be preferred:
PriorityQueue<Task> pq4 = new PriorityQueue<>( // (5)
Comparator.comparing(Task::getTaskName).reversed()
);