Bucket queue

The bucket queue is the priority-queue analogue of pigeonhole sort (also called bucket sort), a sorting algorithm that places elements into buckets indexed by their priorities and then concatenates the buckets. Using a bucket queue as the priority queue in a selection sort gives a form of the pigeonhole sort algorithm. Bucket queues are also called bucket priority queues or bounded-height priority queues. When used for quantized approximations to real number priorities, they are also called untidy priority queues or pseudo priority queues. They are closely related to the calendar queue, a structure that uses a similar array of buckets for exact prioritization by real numbers.

Applications of the bucket queue include computation of the degeneracy of a graph, fast algorithms for shortest paths and widest paths for graphs with weights that are small integers or are already sorted, and greedy approximation algorithms for the set cover problem. The quantized version of the structure has also been applied to scheduling and to marching cubes in computer graphics. The first use of the bucket queue was in a shortest path algorithm by Dial (1969).

Operation

Basic data structure

A bucket queue can handle elements with integer priorities in the range from 0 or 1 up to some known bound C, and operations that insert elements, change the priority of elements, or extract (find and remove) the element that has the minimum (or maximum) priority. It consists of an array A of container data structures; in most sources these containers are doubly linked lists but they could alternatively be dynamic arrays or dynamic sets. The container in the pth array cell A[p] stores the collection of elements whose priority is p.

A bucket queue can handle the following operations:

• To insert an element x with priority p, add x to the container at A[p].
• To change the priority of an element, remove it from the container for its old priority and re-insert it into the container for its new priority.
• To extract an element with the minimum or maximum priority, perform a sequential search in the array to find the first or last non-empty container, respectively, choose an arbitrary element from this container, and remove it from the container.

In this way, insertions and priority changes take constant time, and extracting the minimum or maximum priority element takes time O(C).

Optimizations

As an optimization, the data structure can start each sequential search for a non-empty bucket at the most recently-found non-empty bucket instead of at the start of the array. This can be done in either of two different ways, lazy (delaying these sequential searches until they are necessary) or eager (doing the searches ahead of time). The choice of when to do the search affects which of the data structure operations is slowed by these searches. Dial's original version of the structure used a lazy search. This can be done by maintaining an index L that is a lower bound on the minimum priority of any element currently in the queue. When inserting a new element, L should be updated to the minimum of its old value and the new element's priority. When searching for the minimum priority element, the search can start at L instead of at zero, and after the search L should be left equal to the priority that was found in the search. Alternatively, the eager version of this optimization keeps L updated so that it always points to the first non-empty bucket. When inserting a new element with a priority smaller than L, the data structure sets L to the new priority, and when removing the last element from a bucket with priority L, it performs a sequential search through larger indexes until finding a non-empty bucket and setting L to the priority of the resulting bucket.

In either of these two variations, each sequential search takes time proportional to the difference between the old and new values of L. This could be significantly faster than the O(C) time bound for the searches in the un-optimized version of the data structure. In many applications of priority queues such as Dijkstra's algorithm, the minimum priorities form a monotonic sequence, allowing a monotone priority queue to be used. In these applications, for both the lazy and eager variations of the optimized structure, the sequential searches for non-empty buckets cover disjoint ranges of buckets. Because each bucket is in at most one of these ranges, their numbers of steps add to at most C. Therefore, in these applications, the total time for a sequence of n operations is O(n + C), rather than the slower O(nC) time bound that would result without this optimization. A corresponding optimization can be applied in applications where a bucket queue is used to find elements of maximum priority, but in this case it should maintain an index that upper-bounds the maximum priority, and the sequential search for a non-empty bucket should proceed downwards from this upper bound.

Another optimization (already given by Dial 1969) can be used to save space when the priorities are monotonic and, throughout the course of an algorithm, always fall within a range of r values rather than extending over the whole range from 0 to C. In this case, one can index the array by the priorities modulo r rather than by their actual values. The search for the minimum priority element should always begin at the previous minimum, to avoid priorities that are higher than the minimum but have lower moduli. In particular, this idea can be applied in Dijkstra's algorithm on graphs whose edge lengths are integers in the range from 1 to r.

Because creating a new bucket queue involves initializing an array of empty buckets, this initialization step takes time proportional to the number of priorities. A variation of the bucket queue described by Donald B. Johnson in 1981 instead stores only the non-empty buckets in a linked list, sorted by their priorities, and uses an auxiliary search tree to quickly find the position in this linked list for any new buckets. It takes time O(log log C) to initialize this variant structure, constant time to find an element with minimum or maximum priority, and time O(log log D) to insert or delete an element, where D is the difference between the nearest smaller and larger priorities to the priority of the inserted or deleted element.

Example

For example, consider a bucket queue with four priorities, the numbers 0, 1, 2, and 3. It consists of an array ${\displaystyle A}$ whose four cells each contain a collection of elements, initially empty. For the purposes of this example, ${\displaystyle A}$ can be written as a bracketed sequence of four sets: ${\displaystyle A=[\mathrm{\varnothing },\mathrm{\varnothing },\mathrm{\varnothing },\mathrm{\varnothing }]}$. Consider a sequence of operations in which we insert two elements ${\displaystyle x}$ and ${\displaystyle y}$ with the same priority 1, insert a third element ${\displaystyle z}$ with priority 3, change the priority of ${\displaystyle x}$ to 3, and then perform two extractions of the minimum-priority element.

• After inserting ${\displaystyle x}$ with priority 1, ${\displaystyle A=[\mathrm{\varnothing },\{x\},\mathrm{\varnothing },\mathrm{\varnothing }]}$.
• After inserting ${\displaystyle y}$ with priority 1, ${\displaystyle A=[\mathrm{\varnothing },\{x,y\},\mathrm{\varnothing },\mathrm{\varnothing }]}$.
• After inserting z with priority 3, ${\displaystyle A=[\mathrm{\varnothing },\{x,y\},\mathrm{\varnothing },\{z\}]}$.
• Changing the priority of x from 1 to three involves removing it from ${\displaystyle A[1]}$ and adding it to ${\displaystyle A[3]}$, after which ${\displaystyle A=[\mathrm{\varnothing },\{y\},\mathrm{\varnothing },\{x,z\}]}$.
• Extracting the minimum-priority element, in the basic version of the bucket queue, searches from the start of ${\displaystyle A}$ to find its first non-empty element: ${\displaystyle A[0]}$ is empty but ${\displaystyle A[1]=\{y\}}$, a non-empty set. It chooses an arbitrary element of this set (the only element, ${\displaystyle y}$) as the minimum-priority element. Removing ${\displaystyle y}$ from the structure leaves ${\displaystyle A=[\mathrm{\varnothing },\mathrm{\varnothing },\mathrm{\varnothing },\{x,z\}]}$.
• The second extract operation, in the basic version of the bucket queue, searches again from the start of the array: ${\displaystyle A[0]=\mathrm{\varnothing }}$, ${\displaystyle A[1]=\mathrm{\varnothing }}$, ${\displaystyle A[2]=\mathrm{\varnothing }}$, ${\displaystyle A[3]=}$non-empty. In the improved variants of the bucket queue, this search starts instead at the last position that was found to be non-empty, ${\displaystyle A[1]}$. In either case, ${\displaystyle A[3]=\{x,z\}}$ is found to be the first non-empty set. One of its elements is chosen arbitrarily as the minimum-priority element; for example, ${\displaystyle z}$ might be chosen. This element is removed, leaving ${\displaystyle A=[\mathrm{\varnothing },\mathrm{\varnothing },\mathrm{\varnothing },\{x\}]}$.