File RadixHeap.h

↰ Parent directory (ADS/priority)

A monotone priority queue of integer keys, beyond the book: the radix heap of Ahuja, Mehlhorn, Orlin and Tarjan, in the form with digits of B bits of their two-level heap.

Definition (ADS/priority/RadixHeap.h)

Detailed Description

It serves the algorithms whose extracted keys never decrease, i.e., Dijkstra’s algorithm with nonnegative integer weights and the event simulations, where a key pushed is never smaller than the last one extracted, :math:` ell `.

A key x is a word of W bits (a signed key has its sign bit flipped, which keeps the order), split into :math:` lceil W / B rceil ` digits of B bits. Let r be the digit of the highest bit in which x and :math:` ell ` differ (r = 0 if :math:` x = ell ), and :math: x_r ` the digit r of x: x lies in the bucket :math:` ( r , x_r ) , of index :math: 2^B r + x_r . Since :math: x geq ell ` and the two agree above the digit r, every key of a bucket is smaller than every key of a bucket of larger index, and the keys of a bucket of the row 0 are all equal to :math:` ell ` but for the last digit, i.e., they are equal. Hence the minimum is in the first bucket that is not empty, found by the lowest bit of a mask of the buckets in use; if this bucket is in the row :math:` r > 0 , its least key, kept as the items are pushed, becomes the new :math: ell ` and its items are moved to their buckets for it, all in rows below r. The other buckets keep their items: a key of the row :math:` r’ geq r ` agrees with the new :math:` ell ` in the same digits as with the old one.

Each item thus moves at most :math:` lceil W / B rceil - 1 ` times, so that, with the potential :math:` Phi = sum_x row( x ) , push() takes O( 1 ) time and pop() :math: O( W / B + 2^B W / ( B w ) ) ` amortized, the second term the scan of the mask of :math:` 2^B lceil W / B rceil ` bits in words of w = 64; for the keys of a band of width C above :math:` ell ` only the :math:` lceil log_2 ( C + 1 ) / B rceil ` lowest rows are ever used. With B = 1 it is the radix heap of the paper, :math:` O( log C ) ` amortized per pop(); larger digits trade fewer moves for more buckets, as in the two-level heap of the paper. The buckets are vectors that keep their memory, so that a queue in a steady state calls no allocator, and the items of a bucket come out last pushed first.

The contracts [see File Contract.h]: a key pushed is not smaller than the last one extracted or read by top() and topKey() (any key before the first of them and after clear()), and top(), topKey(), peekKey() and pop() need a queue that is not empty; the invariant, checked on queues of at most 1024 items, is that each item is in its bucket and that the mask and the least keys of the buckets are right. The operations are defined in RadixHeap.tpp.

    1. Ahuja, K. Mehlhorn, J. Orlin, R. E. Tarjan, Faster algorithms for the shortest path problem, Journal of the ACM 37(2), 213-223, 1990, doi:10.1145/77600.77615

    1. Cherkassky, A. V. Goldberg, T. Radzik, Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming 73(2), 129-174, 1996, doi:10.1007/BF02592101

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

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

  • ADS/priority/impl/RadixHeap.tpp

  • array

  • bit

  • concepts

  • cstddef

  • cstdint

  • limits

  • type_traits

  • utility

  • vector

Included By

Namespaces

Classes