Radix heap
![]() | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (September 2017) |
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.
- Heaps (data structures)