Bucket queue

Basic data structure A bucket queue can handle elements with integer priorities in the range from 0 or 1 up to some known bound , 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 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 th array cell stores the collection of elements whose priority A bucket queue can handle the following operations: • To insert an element with priority , add to the container at . • 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 . 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 that is a lower bound on the minimum priority of any element currently in the queue. 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. Example For example, consider a bucket queue with four priorities, the numbers 0, 1, 2, and 3. It consists of an array A whose four cells each contain a collection of elements, initially empty. For the purposes of this example, A can be written as a bracketed sequence of four sets: A = [\emptyset, \emptyset, \emptyset, \emptyset]. Consider a sequence of operations in which we insert two elements x and y with the same priority 1, insert a third element z with priority 3, change the priority of x to 3, and then perform two extractions of the minimum-priority element. • After inserting x with priority 1, A = [\emptyset, \{x\}, \emptyset, \emptyset]. • After inserting y with priority 1, A = [\emptyset, \{x,y\}, \emptyset, \emptyset]. • After inserting z with priority 3, A = [\emptyset, \{x,y\}, \emptyset, \{z\}]. • Changing the priority of x from 1 to three involves removing it from A[1] and adding it to A[3], after which A = [\emptyset, \{y\}, \emptyset, \{x,z\}]. • Extracting the minimum-priority element, in the basic version of the bucket queue, searches from the start of A to find its first non-empty element: A[0] is empty but A[1] = \{y\}, a non-empty set. It chooses an arbitrary element of this set (the only element, y) as the minimum-priority element. Removing y from the structure leaves A = [\emptyset, \emptyset, \emptyset, \{x,z\}]. • The second extract operation, in the basic version of the bucket queue, searches again from the start of the array: A[0] = \emptyset, A[1] = \emptyset, A[2] = \emptyset, 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, A[1]. In either case, 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, z might be chosen. This element is removed, leaving A = [\emptyset, \emptyset, \emptyset, \{x\}]. ==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. Dial's algorithm for shortest paths In Dijkstra's algorithm for shortest paths in directed graphs with edge weights that are positive integers, the priorities are monotone, and a monotone bucket queue can be used to obtain a time bound of , where 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. In this quantized version of the algorithm, the vertices are processed out of order, compared to the result with a non-quantized priority queue, but the correct shortest paths are still found. In these algorithms, the priorities will only span a range of width , so the modular optimization can be used to reduce the space to . Greedy set cover The set cover problem has as its input a family of sets. The output should be a subfamily of these sets, with the same union as the original family, including as few sets as possible. 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 sizes of the input sets. The priorities are monotonically decreasing integers, upper-bounded by the number of elements to be covered. 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. The total time is linear in the input size. 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 monotone, so fast marching can use the monotone optimization of the bucket queue and its analysis. However, the discretization introduces some error into the resulting calculations. ==See also==