Radix heap

<h2 id="prerequisites">Prerequisites</h2>
<ol><li>all keys are <a href="/facts/Natural_numbers/u65og8JE">natural numbers</a>;</li>
<li>max. key - min. key 
 
 
 
 ≤
 
 
 {\displaystyle \leq }
 
 C for constant C;</li>
<li>the <a href="/facts/Heap_(data_structure)/A67B0K7L">extract-min operation</a> is monotonic; that is, the values returned by successive extract-min calls are <a href="/facts/Monotonically_increasing/MjQK0YL2">monotonically increasing</a>.</li></ol>
<h2 id="description-of-data-structure">Description of data structure</h2>
The three most important <a href="/facts/Field_(computer_science)/jt622EDb">fields</a> are:

<ol><li>
 
 
 
 b
 
 
 {\displaystyle b}
 
 of size 
 
 
 
 B
 :=
 ⌊
 l
 o
 g
 (
 C
 +
 1
 )
 ⌋
 +
 1
 
 
 {\displaystyle B:=\lfloor log(C+1)\rfloor +1}
 
, with 0 as the lowest index, stores the buckets;</li>
<li>
 
 
 
 u
 
 
 {\displaystyle u}
 
 of size 
 
 
 
 B
 +
 1
 
 
 {\displaystyle B+1}
 
, with 0 as the lowest index, store the (lower) bounds of the buckets;</li>
<li>
 
 
 
 b
 N
 u
 m
 
 
 {\displaystyle bNum}
 
, holds for each element 
 
 
 
 x
 
 
 {\displaystyle x}
 
 in the heap the bucket in which it is stored.</li></ol>
The above diagram shows the data structure. The following invariants apply:

<ol><li>
 
 
 
 u
 [
 i
 ]
 ≤
 
 
 {\displaystyle u[i]\leq }
 
 key in 
 
 
 
 b
 [
 i
 ]
 <
 u
 [
 i
 +
 1
 ]
 
 
 {\displaystyle b[i]<u[i+1]}
 
: the keys in 
 
 
 
 b
 [
 i
 ]
 
 
 {\displaystyle b[i]}
 
 are up or down through the value in 
 
 
 
 u
 [
 i
 +
 1
 ]
 
 
 {\displaystyle u[i+1]}
 
 or 
 
 
 
 u
 [
 i
 ]
 
 
 {\displaystyle u[i]}
 
 limited.</li>
<li>
 
 
 
 u
 [
 0
 ]
 =
 0
 ,
 u
 [
 1
 ]
 =
 u
 [
 0
 ]
 +
 1
 ,
 u
 [
 B
 ]
 =
 ∞
 
 
 {\displaystyle u[0]=0,u[1]=u[0]+1,u[B]=\infty }
 
 and 
 
 
 
 0
 ≤
 u
 [
 i
 +
 1
 ]
 −
 u
 [
 i
 ]
 ≤
 
 2
 
 i
 −
 1
 
 
 
 
 {\displaystyle 0\leq u[i+1]-u[i]\leq 2^{i-1}}
 
 for 
 
 
 
 i
 =
 1
 ,
 …
 ,
 B
 −
 1
 
 
 {\displaystyle i=1,\ldots ,B-1}
 
: the sizes of the buckets increase exponentially.</li></ol>
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.

<h2 id="operations">Operations</h2>
During initialization, empty buckets are generated and the lower bounds 
 
 
 
 u
 
 
 {\displaystyle u}
 
 are generated (according to invariant 2); running time 
 
 
 
 O
 (
 B
 )
 
 
 {\displaystyle O(B)}
 
.
During insert, a new element 
 
 
 
 x
 
 
 {\displaystyle x}
 
 is linearly moved from right to left through the buckets and the new element with 
 
 
 
 k
 (
 x
 )
 
 
 {\displaystyle k(x)}
 
 is stored in the left bucket to that 
 
 
 
 u
 [
 i
 ]
 ≥
 k
 (
 x
 )
 
 
 {\displaystyle u[i]\geq k(x)}
 
; running time 
 
 
 
 O
 (
 B
 )
 
 
 {\displaystyle O(B)}
 
.
For decrease-key, first the key value is decreased (checking for compliance with the invariants). Then, the 
 
 
 
 b
 N
 u
 m
 
 
 {\displaystyle bNum}
 
 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 
 
 
 
 O
 (
 1
 )
 
 
 {\displaystyle O(1)}
 
 (amortized).
The extract-min operation removes an element from bucket 
 
 
 
 b
 [
 0
 ]
 
 
 {\displaystyle b[0]}
 
 and returns it. If the bucket 
 
 
 
 b
 [
 0
 ]
 
 
 {\displaystyle b[0]}
 
 is not yet empty, the operation is terminated. If, however, it is empty, the next larger non-empty bucket is searched, its smallest element 
 
 
 
 k
 
 
 {\displaystyle k}
 
 tracked and 
 
 
 
 u
 [
 0
 ]
 
 
 {\displaystyle u[0]}
 
 is set to k (monotonicity is required for this). Then, according to the invariants, the bucket boundaries are redefined and the elements removed 
 
 
 
 b
 [
 i
 ]
 
 
 {\displaystyle b[i]}
 
 to the newly formed buckets; running time 
 
 
 
 O
 (
 1
 )
 
 
 {\displaystyle O(1)}
 
 (amortized).
If displayed, the field 
 
 
 
 b
 N
 u
 m
 
 
 {\displaystyle bNum}
 
 is updated.

<ul><li>B.V. Cherkassky, A.V. Goldberg, C. Silverstein: <a href="http://xenon.stanford.edu/~csilvers/papers/hotq-soda.ps">Buckets, Heaps, Lists and Monotone Priority Queues</a> (<a href="http://xenon.stanford.edu/~csilvers/papers/hotq-soda-abstract.txt">Abstract</a>), in: Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms. January 1997, pp. 83-92.</li></ul>

Radix heap open-in-new

Radix heap