A PriorityQueue is a queue
- a sorted order is permanently imposed on the items it contains;
- in queue terms, the highest-priority element is at the head of the queue
(and the lowest is at the tail of the queue);
- queue operations are efficient: that is, removing the highest-priority element
and adding any element are both efficient operations;
- non-queue operations (such as searching for an item that isn't at the head
of the queue) are not efficient1.
By default, "high priority" is defined to mean numerically lowest from the
point of view of a Comparator, but it's relatively trivial
to reverse that by specifying an appropriate comparator.
Remember that a queue
in general is essentially a structure optimised to add things to one end and remove them from the other.
With a priority queue, we can envisage this queue as a permanently-sorted list,
so that the highest priority element is always at one end and the lowest-priority element at the other.
In this case, we don't actually add an element to the "end": each element added is automatically
slotted in to the relevant place in the list depending on its priority.
When to use PriorityQueue?
A priority queue is useful in a variety of cases where you want to add elements
in any order, but retrieve them in sorted order, and where you don't necessarily
retrieve the elements all at once. In principle, examples are:
- algorithms that need a heap or to make a tree structure out of some data,
such as when building a Huffman compression tree (or any other algorithm you
may have where you need to "sort something gradually", occasionally taking
the topmost elements, altering them, and placing them back into the tree...);
- performing a heapsort (although
this algorithm has largely fallen out of favour nowadays);
- a job scheduler, that accepts tasts to run at different times,
but must know at any moment what the next task is that needs running—
the java.util.Timer class is an example of this functionality
(for historical reasons, Timer actually has its own queue implementation,
but that's just because the Java queue classes weren't added until Java 5);
in this case, "priority" is effectively the clock time at which the job
needs to run, with a lower time equalling higher priority; note that
in real life, ScheduledThreadPoolExecutor may be a better
alternative unless you need some special functionality;
- code that receives and processes jobs "immediately" but with different priorities, such as a server that runs
commands; at any time it has a spare thread, it needs to know what is the next
highest priority job to give to that thread; note that
BlockingQueue isn't synchronized, and whilst you could add
explicit synchronization, it's usually better to use its cousin
PriorityBlockingQueue when you need a priority queue with concurrent access.
Having just said that it's not a typical use nowadays, our
PriorityQueue example will nonetheless
show how to perform a one-off sort of data, as it will introduce the principal
methods of the PriorityQueue class.
Data structure of a PriorityQueue
As mentioned, we can imaging a priority queue as a sorted list.
But literally using a simple list structure would be inefficent.
For example, if the queue is 200 elements long and we need to insert an item in slot 3,
we need to move 197 elements, and in general, the number of items we expect to move on
average would grow linearly with the size of the queue.
So the structure
actually used is a binary heap. That is, a binary tree in which the value of a node is always
greater than or equal to the value of its two children. This structure makes it efficient
to insert an item in its sorted place and remove the highest-priority item, since the maximum
number of items we need to move in either case is the number of levels in the tree,
rather than the number of items (as would be the case if we used a simple list).
So, on the next page, we give an example of
using PriorityQueue to perform a heapsort.
1. By efficient, we mean the time taken to perform
operations grows less than linearly as the size of the structure grows. So if
the time with 5 elements is 500 nanoseconds, the time with 10 elements is less
than 1000 nanoseconds etc.