Radix heap

A radix heap is a data structure for realizing the operations of a monotone priority queue. A set of elements to which a key is assigned can then be managed. The run time of the operations depends on the difference between the largest and smallest key or constant. The data structure consists mainly of a series of buckets, the size of which increases exponentially.

Prerequisites
 all keys are natural numbers;
 max. key - min. key  C for constant C;
 the extract-min operation is monotonic; that is, the values returned by successive extract-min calls are monotonically increasing.

Description of data structure
The three most important fields are:
  of size , with 0 as the lowest index, stores the buckets;
  of size , with 0 as the lowest index, store the (lower) bounds of the buckets;
 , holds for each element  in the heap the bucket in which it is stored.

The above diagram shows the data structure. The following invariants apply:

  key in : the keys in  are up or down through the value in  or  limited.
  and  for : the sizes of the buckets increase exponentially.

It is important to note the exponential growth of the limits (and thus the range that a bucket holds). In this way the logarithmic dependence of the field quantities is of value C, the maximum difference between two key values.

Operations

During initialization, empty buckets are generated and the lower bounds  are generated (according to invariant 2); running time .

During insert, a new element  is linearly moved from right to left through the buckets and the new element with  is stored in the left bucket to that ; running time .

For decrease-key, first the key value is decreased (checking for compliance with the invariants).  Then, the  field is used to locate the element and it is iterated to the left, if necessary, analogously to the insert operation.  The running time is  (amortized).

The extract-min operation removes an element from bucket  and returns it. If the bucket  is not yet empty, the operation is terminated. If, however, it is empty, the next larger non-empty bucket is searched, its smallest element  tracked and  is set to k (monotonicity is required for this). Then, according to the invariants, the bucket boundaries are redefined and the elements removed  to the newly formed buckets; running time  (amortized).

If displayed, the field  is updated.

References
 B.V. Cherkassky, A.V. Goldberg, C. Silverstein: Buckets, Heaps, Lists and Monotone Priority Queues (Abstract), in: Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms. January 1997, pp. 83-92.

Category: Data structures