Bucket queue

In the design and analysis of data structures, a bucket queue (also called a bucket priority queue or bounded-height priority queue) 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. With this data structure, insertion or removal of elements takes constant time. Searches for the minimum-priority element take time proportional to the number of buckets or, by maintaining a pointer to the most recently found bucket, in time proportional to the difference in priorities between the results of successive searches.
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. When used for quantized approximations to real number priorities, it has also been called an untidy priority queue or pseudo priority queue, and is closely related to the calendar queue structure 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 .
Operation.
Basic data structure.
This structure can handle the insertions and deletions of elements with integer priorities in the range from 0 or 1 to some known bound , as well as operations that find the element with minimum (or maximum) priority. It consists of an array of container data structures, where array cell stores the collection of elements with priority .
It can handle the following operations:
In this way, insertions and removals take constant time, and finding the minimum or maximum priority element takes time .
Optimizations.
As an optimization, the data structure can also maintain an index that lower-bounds the minimum priority of an element. When inserting a new element, 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 instead of at zero, and after the search should be left equal to the priority that was found in the search. In this way the time to search for the minimum-priority element is reduced to the difference between the previous lower bound and its next value; this difference could be significantly smaller than . In many applications of monotone priority queues such as Dijkstra's algorithm, the minimum priorities form a monotonic sequence, so the sequential searches for non-empty buckets cover disjoint ranges of buckets, and their numbers of steps add in a telescoping series to at most . Therefore, in these applications, the total time for a sequence of operations is , rather than the slower 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 ) can be used to save space when the priorities are monotonic and, throughout the course of an algorithm, always fall within a range of values rather than extending over the whole range from 0 to . In this case, one can index the array by the priorities modulo 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 .
Applications.
Graph degeneracy.
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. 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.
Dial's algorithm for shortest paths.
In Dijkstra's algorithm for shortest paths in directed graphs with edge weights that are positive integers, a bucket queue can be used to obtain a time bound of , where is the number of vertices, is the number of edges, is the diameter of the network, and is the maximum (integer) link cost. This variant of Dijkstra's algorithm is also known as Dial's algorithm, after Robert B. Dial, who published it in 1969. It can also be used, with a quantized bucket queue, to compute the correct shortest paths in a graph with positive real edge weights when the ratio of the maximum to minimum weight is at most ; in this version of the algorithm, the vertices are processed out of order, compared to the result with a non-quantized priority queue, but the changes of ordering do not affect the overall results. In these algorithms, the priorities will only span a range of width , so the modular optimization can be used to reduce the space to .
A variant of the same algorithm can be used for the widest path problem. In combination with methods for quickly partitioning non-integer edge weights into subsets that can be assigned integer priorities, it leads to near-linear-time solutions to the single-source single-destination version of the widest path problem.
Greedy set cover.
The set cover problem has as its input a family of sets, with the desired output being a subfamily of as few sets as possible having the same union.
It is NP-hard, but has a greedy approximation algorithm that achieves a logarithmic approximation ratio, essentially the best possible unless P = NP. This approximation algorithm selects its subfamily by repeatedly choosing a set that covers the maximum possible number of remaining uncovered elements. A standard exercise in algorithm design asks for an implementation of this algorithm that takes linear time in the input size, which is the sum of sizes of all the input sets.
This may be solved using a bucket queue of sets in the input family, prioritized by the number of remaining elements that they cover. Each time that the greedy algorithm chooses a set as part of its output, the newly covered set elements should be subtracted from the priorities of the other sets that cover them; over the course of the algorithm the number of these changes of priorities is just the sum of set sizes. The priorities are monotonically decreasing integers, and each choice of the greedy algorithm involves finding the set with the maximum priority, which can be done by scanning downwards through the buckets of the bucket queue, starting from the most recent previous maximum value. In this way, the total time for the data structure to find these sets is proportional to the maximum initial priority, which is at most the number of elements to be covered.
Scheduling.
Bucket queues can be used to schedule tasks with deadlines, for instance in packet forwarding for internet data with quality of service guarantees. For this application, the deadlines should be quantized into discrete intervals, and tasks whose deadlines fall into the same interval are considered to be of equivalent priority.
A variation of the quantized bucket queue data structure, the calendar queue, has been applied to scheduling of discrete-event simulations, where the elements in the queue are future events prioritized by the time within the simulation that the events should happen. In this application, the ordering of events is critical, so the priorities cannot be approximated. Therefore, the calendar queue performs searches for the minimum-priority element in a different way than a bucket queue: in the bucket queue, any element of the first non-empty bucket may be returned, but instead the calendar queue searches all the elements in that bucket to determine which of them has the smallest non-quantized priority. To keep these searches fast, this variation attempts to keep the number of buckets proportional to the number of elements, by adjusting the scale of quantization and rebuilding the data structure when it gets out of balance. Calendar queues may be slower than bucket queues in the worst case (when many elements all land in the same smallest bucket) but are fast when elements are uniformly distributed among buckets causing the average bucket size to be constant.
Fast marching.
In applied mathematics and numerical methods for the solution of differential equations, untidy priority queues have been used to prioritize the steps of the fast marching method for solving boundary value problems of the Eikonal equation, used to model wave propagation. This method finds the times at which a moving boundary crosses a set of discrete points (such as the points of an integer grid) using a prioritization method resembling a continuous version of Dijkstra's algorithm, and its running time is dominated by its priority queue of these points. It can be sped up to linear time by rounding the priorities used in this algorithm to integers, and using a bucket queue for these integers. As in Dijkstra's and Dial's algorithms, the priorities are monototonic, so the telescoping analysis of the bucket queue can be used. However, the discretization introduces some error into the resulting calculations.