File BucketQueue.h

↰ Parent directory (ADS/priority)

A priority queue for small nonnegative integer keys, beyond the book: a two-level bucket queue, whose outer level is a vector indexed by the first key f and whose inner one, for each f, a vector of LIFO lists indexed by the second key g.

Definition (ADS/priority/BucketQueue.h)

Detailed Description

top() is an item of least f and, among those, of largest g, the last one pushed (the order that A* wants: least f, ties broken towards the deeper nodes). The least f is found by a scan that only moves forward between two pushes of a smaller f, and the largest g of a layer likewise backward, so that push() takes O( 1 ) time and pop() O( 1 ) amortized when the keys are bounded by C, against the :math:` O( log n ) ` of a heap: the queue of Dial for the shortest paths with integer weights, nested as in the search code of Burns et al.

The items lie in one vector of cells, each with the index of the next cell of its list, and the cells freed by pop() form a list of their own that push() takes from first, so that a push or a pop costs no call to the allocator once the vector has grown to the largest size of the queue. A layer keeps the heads of its first four lists in itself and those of larger g in a vector, which it frees when it empties, so that a layer of small g costs no allocation and the memory follows the band of the keys in the queue: :math:` O( n + F + sum_f G_f ) ` words for n items, F the largest f pushed and :math:` G_f ` the largest g in the layer f while it is in use.

There is no decrease-key: as in the lazy deletion of A*, an item whose key improves is pushed again, and the caller skips the stale copies when they come out.

The contracts [see File Contract.h]: the keys are nonnegative, and top(), topF(), topG() and pop() need a queue that is not empty; the invariant is that the counts of the layers add up to size(). The operations are defined in BucketQueue.tpp.

    1. Dial, Algorithm 360: shortest-path forest with topological ordering, Communications of the ACM 12(11), 632-633, 1969, doi:10.1145/363269.363610

  1. Burns, M. Hatem, M. J. Leighton, W. Ruml, Implementing fast heuristic search code, Proceedings of the 5th Symposium on Combinatorial Search (SoCS), 25-32, 2012

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/priority/impl/BucketQueue.tpp

  • concepts

  • cstddef

  • cstdint

  • iterator

  • utility

  • vector

Namespaces

Classes