bucketqueue

Bucket queue is a data structure used as a priority queue for nonnegative integer priorities within a known finite range. It consists of an array of buckets, where bucket i holds all elements whose priority (key) equals i. The design allows fast insertion and decrease-key by placing an element into the bucket corresponding to its new priority. A pointer tracks the smallest non-empty bucket, and extracting the minimum advances this pointer to the next non-empty bucket.

One well-known variant is Dial's bucket queue, used with nonnegative integer edge weights in shortest-path algorithms. In Dial's approach, the maximum weight W determines the number of buckets. When a vertex’s tentative distance decreases to d, it is moved to bucket d. To extract the next vertex with the smallest distance, the algorithm scans buckets from the current index until a non-empty bucket is found, removing an element from that bucket. In graphs, the time complexity is O(m + n + W), with O(1) amortized time for individual insertions, deletions, and key updates, assuming W is not too large relative to n and m.

Variants and enhancements include circular or multilevel bucket queues to handle larger or changing weight ranges, and radix-heap approaches that extend bucket-like ideas to broader domains. Bucket queues are primarily used when all priorities are nonnegative integers with a known bound, enabling efficient non-decreasing key progress in algorithms such as Dijkstra’s algorithm, the single-source shortest path in dense graphs, or discrete-event simulations.

Limitations include the requirement of a bounded weight range and nonnegative keys; memory usage grows with W; they are not suitable for arbitrary real-valued or negative priorities, or when the bound is large relative to the problem size. In such cases, traditional binary heaps or Fibonacci heaps may be preferable.