PriorityQueue

A PriorityQueue is a queue where:

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:

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


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.