PriorityQueue

A PriorityQueue is a queue where:

• 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 efficient¹.

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).

Next

So, on the next page, we give an example of using PriorityQueue to perform a heapsort.

See also...

• Java queue classes

---

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.

---