Bucket queue

In the design and analysis of data structures, a bucket queue^[1] (also called a bucket priority queue^[2] or bounded-height priority queue^[3]) is a priority queue for prioritizing elements whose priorities are small integers. It has the form of an array of buckets: an array data structure, indexed by the priorities, whose cells contain buckets of items with the same priority as each other.

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.

Applications of the bucket queue include computation of the degeneracy of a graph as well as fast algorithms for shortest paths and widest paths for graphs with weights that are small integers or are already sorted. Its first use^[2] was in a shortest path algorithm by Dial (1969).^[4]

Basic data structure

This structure can handle the insertions and deletions of elements with integer priorities in the range from 0 to some known bound C, as well as operations that find the element with minimum (or maximum) priority. It consists of an array A of container data structures, where array cell A[p] stores the collection of elements with priority p. It can handle the following operations:

• To insert an element x with priority p, add x to the container at A[p].
• To remove an element x with priority p, remove x from the container at A[p]
• To find an element with the minimum priority, perform a sequential search to find the first non-empty container, and then choose an arbitrary element from this container.

In this way, insertions and deletions take constant time, while finding the minimum priority element takes time O(C).^[1][3]

Optimizations

As an optimization, the data structure can also maintain an index L that lower-bounds the minimum priority of an element. 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.^[3] In this way the time for a search is reduced to the difference between the previous lower bound and its next value; this difference could be significantly smaller than C. For applications of monotone priority queues such as Dijkstra's algorithm in which the minimum priorities form a monotonic sequence, the sum of these differences is at most C, so 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.

Another optimization (already given by Dial 1969) can be used to save space when the priorities are monotonic and, at any point in time, 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.^[1]

Applications

A bucket queue can be used to maintain the vertices of an undirected graph, prioritized by their degrees, and repeatedly find and remove the vertex of minimum degree.^[3] This greedy algorithm can be used to calculate the degeneracy of a given graph. It takes linear time, with or without the optimization that maintains a lower bound on the minimum priority, because each vertex is found in time proportional to its degree and the sum of all vertex degrees is linear in the number of edges of the graph.^[5]

In Dijkstra's algorithm for shortest paths in positively-weighted directed graphs, a bucket queue can be used to obtain a time bound of O(n + m + dc), where n is the number of vertices, m is the number of edges, d is the diameter of the network, and c is the maximum (integer) link cost.^[6] In this algorithm, the priorities will only span a range of width c + 1, so the modular optimization can be used to reduce the space to O(n + c).^[1] A variant of the same algorithm can be used for the widest path problem, and (in combination with methods for quickly partitioning non-integer edge weights) leads to near-linear-time solutions to the single-source single-destination version of this problem.^[7]

References