Radix Heap

Ein Radix Heap ist eine Datenstruktur zur Realisation der Operationen einer Vorrangwarteschlange. Hiermit kann dann eine Menge von Elementen, denen jeweils ein Schlüssel zugeordnet ist, verwaltet werden. Die Laufzeit der Operationen ist abhängig von der Differenz des größten und kleinsten Schlüssels bzw. konstant. Die Datenstruktur besteht hauptsächlich aus einer Reihe von Buckets (von engl. bucket „Eimer“), deren Größe exponentiell zunimmt.

Voraussetzungen

1. alle Schlüssel sind aus den natürlichen Zahlen
2. max. Schlüssel – min. Schlüssel ${\displaystyle \leq }$ C für ein festes C
3. Monotonie von extractMin, d. h. die von aufeinander folgenden extractMin-Aufrufen zurückgegebenen Werte sind monoton steigend.

Beschreibung der Datenstruktur

Die d​rei wichtigsten Felder sind:

1. ${\displaystyle b}$ der Größe ${\displaystyle B:=\lfloor \log(C+1)\rfloor +1}$, mit 0 als niedrigstem Index; speichert die Buckets
2. ${\displaystyle u}$ der Größe ${\displaystyle B+1}$, mit 0 als niedrigstem Index; speichert die (unteren) Schranken der Buckets
3. ${\displaystyle bNum}$, hält für jedes Element ${\displaystyle x}$ im Heap den Bucket in dem es gespeichert ist

In d​er obigen Skizze i​st die Datenstruktur n​och einmal skizziert. Zu beachten i​st nun, d​ass stets d​ie folgenden Invarianten gelten müssen:

1. ${\displaystyle u[i]\leq }$ Schlüssel in ${\displaystyle b[i]<u[i+1]}$: die Schlüssel in ${\displaystyle b[i]}$ sind nach oben bzw. unten durch die Werte in ${\displaystyle u[i+1]}$ bzw. ${\displaystyle u[i]}$ beschränkt.
2. ${\displaystyle u[0]=0,u[1]=u[0]+1,u[B]=\infty }$ und ${\displaystyle 0\leq u[i+1]-u[i]\leq 2^{i-1}}$ für ${\displaystyle i=1,\ldots ,B-1}$: die Größen der Buckets nehmen exponentiell zu.

Zu beachten ist das exponentielle Wachstum der Schranken (und damit des Bereiches, den ein Bucket fasst). Hierdurch kommt die logarithmische Abhängigkeit der Feldgrößen zum Wert ${\displaystyle C}$, der maximalen Differenz zweier Schlüsselwerte.

Operationen

Während der Initialisierung werden leere Buckets erzeugt und die unteren Schranken ${\displaystyle u}$ berechnet (gemäß der Invariante 2); Laufzeit ${\displaystyle O(B)}$.

Beim insert eines neuen Elements ${\displaystyle x}$ wird linear von rechts nach links durch die Buckets gegangen und das neue Element mit ${\displaystyle k(x)}$ wird in den linkesten Bucket gespeichert, so dass gilt: ${\displaystyle u[i]\geq k(x)}$. Laufzeit ${\displaystyle O(B)}$.

Bei decreaseKey wird nun das Feld ${\displaystyle bNum}$ benötigt. Von dem nun bekannten Bucket aus wird analog zur Operation insert nun nach der Dekrementierung des Schlüsselwertes nach links iteriert (es muss zusätzlich auf Einhaltung der Invarianten geprüft werden); Laufzeit ${\displaystyle O(1)}$ (amortisiert).

Die Operation extractMin gibt ein Element aus dem Bucket ${\displaystyle b[0]}$ zurück und entfernt es. Ist der Bucket ${\displaystyle b[0]}$ noch nicht leer, so ist die Operation beendet. Ist er jedoch nun leer, so wird der nächstgrößere nicht leere Bucket gesucht, dessen kleinstes Element ${\displaystyle k}$ ausfindig gemacht und ${\displaystyle u[0]}$ auf k gesetzt (hierfür wird die Monotonie benötigt). Dann werden gemäß der Invarianten die Bucketgrenzen neu bestimmt und die Elemente aus ${\displaystyle b[i]}$ auf die neu entstandenen Buckets aufgeteilt; Laufzeit ${\displaystyle O(1)}$ (amortisiert).

Wenn jeweils angezeigt, dann muss zusätzlich das Feld ${\displaystyle bNum}$ aktualisiert werden.

Literatur

• 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. Januar 1997, S. 83–92.