Java Reference
In-Depth Information
When removing an element from a priority queue, the element with the highest
priority is retrieved.
It is customary to give low values to high priorities, with priority 1 denoting the
highest priority. The priority queue extracts the minimum element from the queue.
For example, consider this sample code:
PriorityQueue<WorkOrder> q = new
PriorityQueue<WorkOrder>;
q.add(new WorkOrder(3, ÐShampoo carpetsÑ));
q.add(new WorkOrder(1, ÐFix overflowing sinkÑ));
q.add(new WorkOrder(2, ÐOrder cleaning suppliesÑ));
When calling
q.remove()
for the first time, the work order with priority 1 is
removed. The next call to
q.remove()
removes the work order whose priority is
highest among those remaining in the queueȌin our example, the work order with
priority 2.
The standard Java library supplies a
PriorityQueue
class that is ready for you to
use. Later in this chapter, you will learn how to supply your own implementation.
739
740
Keep in mind that the priority queue is an abstract data type. You do not know how a
priority queue organizes its elements. There are several concrete data structures that
can be used to implement priority queues.
Of course, one implementation comes to mind immediately. Just store the elements in
a linked list, adding new elements to the head of the list. The
remove
method then
traverses the linked list and removes the element with the highest priority. In this
implementation, adding elements is quick, but removing them is slow.
Another implementation strategy is to keep the elements in sorted order, for example
in a binary search tree. Then it is an easy matter to locate and remove the largest
element. However, another data structure, called a heap, is even more suitable for
implementing priority queues.
16.9 Heaps
A heap (or, for greater clarity, min-heap) is a binary tree with two special properties.
