Radix-Heaps

Radix-Heaps stellen eine Möglichkeit zur effizienten Realisierung von Priority-Queues dar, wobei ähnliche Randbedingungen wie bei den 2-Level-Buckets vorausgesetzt werden. Dabei wird die amortisierte Laufzeit der langsamsten Zugriffsfunktion im Vergleich zu diesen verbessert, ähnlich von $\mathcal{O}(\sqrt{C})$ auf $\mathcal{O}(\log C)$. C bezeichne wie bei den 2-Level-Bauckets die maximale Differenz zwischen zwei Schlüsseln im Heap.
Die Grundidee besteht darin, anstelle einer Hierarchie von Buckets konstanter Größe, Buckets mit exponentiell zunehmender Größe zu verwenden. Somit sind nur noch $\mathcal{O}(\log C)$ Buckets zur Verwaltung der Elemente im Heap nötig. Wie bei 2-Level-Buckets hängt die Laufzeit der ``teueren`` Operationen direkt von der Anzahl der Buckets ab.

Randbedingung:

• Schlüssel $\in \mathbbm{N}_0$
• max-Schlüssel - min-Schlüssel stets $\leq$ C
• Monotonie von ExtractMin

Implementierung:

• B$:=\lceil\log(C+1)\rceil+1$
• Buckets $b[0..\text{B}]$
• Schranken für Backets $u[0..\text{B}+1]$ ;
  $u[\text{B}+1]=\infty$
• Bucket-Nr $b\_no[x]$ ; Index der aktuellen Buckets für x
  

Invarianten:

i)

$u[i] \leq \text{Schl\uml {u}ssel in } b[i] \le u[i+1]$

ii)

$u[1]=u[0]+1 \text{\ }; \text{\ }0 \leq u[i+1]-u[i]\leq 2^{i-1} ; \text{ f\uml {u}r } i=1,\dots,\text{B}-1$

Operationen:

1.

Initialize : Leere Buckets erzeugen und die Bucketsgrenzen u[i] entsprechend der Invariante ii) setzen.

for i=0 to B do $b[i]:=\emptyset$ od
		 u[0]=0; u[1]=1;
		 for i=2 to B dou[i]:=u[i-1]+2i-2 od

2.

Insert(x) : Um ein neues Element einzufügen, wird linear nach dem richtigen Buckets gesucht, wobei die Suche beim größten Bucket beginnt.

i:=B;
while u[i]> Key(x) do i:=i-1 od
füge x in b[i] ein;

3.

DecreaseKey(x,K) : Hierbei wird analog zur Prozedur Insert linear nach dem Bucket gesucht, in den das Element mit dem veränderten Schlüssel eingeordnet werden muß. Der einzige Unterschied besteht darin, daß die Suche in diesem Fall beim aktuellen Bucket des Elements beginnen kann, da der Schlüssel erniedrigt wird und das Element deshalb nie in einen größeren Bucket wandern kann. Aus diesem Grund war es notwendig, zu jedem Element x die dazugehörige Bucketnummer in $b\_no[x]$ zu speichern.

		 $i:= b\_no[x]$;		 entferne x aus b[i];
		 Key(x) := k; co Überprüfung, das alles stimmt oc
		 while (u[i]>k) do i:=i-1 od
		 füge x in b[i] ein;  

4.

ExtractMin : Hierbei wird zuerst nach dem kleinsten nicht leeren Bucket gesucht und der kleinste dort enthaltene Schlüssel k festgestellt. Wenn der kleinste Bucket bereits ein Element enthält, so kann dieses ausgegeben werden und es ist sonst nichts zu tun.
Anderfalls wird u[0] auf k gesetzt und die Bucketgrenzen gemäß der Invarianten neu gesetzt. Danach wird ein minimales Element aus dem kleinsten Bucket, der nun nicht mehr leer sein kann, ausgelesen und entfernt. Von dieser ``Aufräumarbeit`` sind nur der kleinste nicht-leere Bucket und die davor liegenden leeren Buckets betroffen.

		 i:=0;
		 Entferne und (und gib zurück) ein beliebiges Element in b[i];
		 if $\char93$ Elemente in Radix-Heap = 0 then return;
		 while $b[i]==\emptyset$ do i:=i+1;
		 k := kleinster Schlüssel in b[i];
		 u[0] = k;
		 u[1] = k+1;
		 for j=2 to i do
		 		 $u[j]=\min\{u[j-1]+2^{j-2},u[i+1]\}$ od
		 od
		 verteile alle Elemente aus b[i] auf $b[0],b[1],\dots,b[i-1]$;  

Beispiel:

$b[i]\neq \emptyset \Rightarrow$ Intervallgröße $\leq 2^{i-1}$
Innerhalb b[i] stehen i-1-Buckets zur Verfügung mit Intervallen $[k,k+1[, [k+2,k+4[,\dots [k+2^{i-2},k+2^{i-1}[$ bzw. höchstens u[i+1]. Da alle Schlüsseln in b[i] aus dem Intervall $[k,\min\{k+2^{i-1}-1,u[i+1]-1\}]$ sind, passen sie alle in $b[0],b[1],\dots,b[i-1]$.

Analyse der amortisierten Kosten:

$$\text{Potential: } \sum_{x \in \text{Radix-Heap}}{b\_no[x]}$$

Amortisierte Komplexität:

i)

Initialize : $\mathcal{O}(1)$ bzw. $\mathcal{O}(B)$

ii)

Insert : $\mathcal{O}(B)$

iii)

DecreaseKey :$\mathcal{O}(\Delta b\_no[x] - \Delta b\_no[x] +1) = \mathcal{O}(1)$

iv)

ExtractMin : $\mathcal{O}(\text{B}+\sum_{x\in b[i]}{\Delta b\_no[x]}-\sum_{x\in b[i]}{\Delta b\_no[x]}) = \mathcal{O}(B) =\mathcal{O}(1)$