Radix heap

A radix heap is a data structure for realizing the operations of a priority queue . This can be used to manage a number of elements, each of which is assigned a key. The runtime of the operations depends on the difference between the largest and smallest key or is constant. The data structure consists mainly of a series of buckets (of English. Bucket " bucket ") whose size exponentially increases.

requirements

all keys are natural numbers
Max. Key - min. Key C for a fixed C. ${\ displaystyle \ leq}$
Monotony of extractMin , d. H. the values returned by successive extractMin calls are monotonically increasing .

Description of the data structure

The three most important fields are:

${\ displaystyle b}$ the size , with 0 as the lowest index; saves the buckets ${\ displaystyle B: = \ lfloor \ log (C + 1) \ rfloor +1}$
${\ displaystyle u}$ the size , with 0 as the lowest index; saves the (lower) bounds of the buckets ${\ displaystyle B + 1}$
${\ displaystyle bNum}$ , holds the bucket in which it is stored for each element in the heap ${\ displaystyle x}$

In the sketch above, the data structure is sketched again. It should now be noted that the following invariants must always apply:

${\ displaystyle u [i] \ leq}$ Keys in : the keys in are limited upwards and downwards by the values in and . ${\ displaystyle b [i] <u [i + 1]}$ ${\ displaystyle b [i]}$ ${\ displaystyle u [i + 1]}$ ${\ displaystyle u [i]}$
${\ displaystyle u [0] = 0, u [1] = u [0] + 1, u [B] = \ infty}$ and for : the sizes of the buckets increase exponentially. ${\ displaystyle 0 \ leq u [i + 1] -u [i] \ leq 2 ^ {i-1}}$ ${\ displaystyle i = 1, \ ldots, B-1}$

Note the exponential growth of the bounds (and thus of the area that a bucket holds). This results in the logarithmic dependence of the field sizes on the value , the maximum difference between two key values . ${\ displaystyle C}$

Operations

During the initialization , empty buckets are created and the lower bounds are calculated (according to invariant 2); Term . ${\ displaystyle u}$ ${\ displaystyle O (B)}$

When insert a new element is gone linearly from right to left through the buckets and the new element is stored in the linkesten bucket, so that: . Term . ${\ displaystyle x}$ ${\ displaystyle k (x)}$ ${\ displaystyle u [i] \ geq k (x)}$ ${\ displaystyle O (B)}$

The field is now required for decreaseKey . From the now known bucket, analogous to the insert operation, it is now iterated to the left after decrementing the key value (it must also be checked that the invariants are adhered to); Term (amortized). ${\ displaystyle bNum}$ ${\ displaystyle O (1)}$

The extractMin operation returns an item from the bucket and removes it. If the bucket is not yet empty, the operation is finished. If, however, it is now empty, the next larger, non-empty bucket is searched for, its smallest element is found and set to k (the monotony is required for this). Then, according to the invariants, the bucket limits are redefined and the elements are distributed to the newly created buckets; Term (amortized). ${\ displaystyle b [0]}$ ${\ displaystyle b [0]}$ ${\ displaystyle k}$ ${\ displaystyle u [0]}$ ${\ displaystyle b [i]}$ ${\ displaystyle O (1)}$

If displayed, the field must also be updated. ${\ displaystyle bNum}$

literature

BV Cherkassky, AV 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.