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. bucketEimer“), deren Größe exponentiell zunimmt.

Voraussetzungen

Bearbeiten
  1. alle Schlüssel sind aus den natürlichen Zahlen
  2. max. Schlüssel – min. Schlüssel   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

Bearbeiten

Die drei wichtigsten Felder sind:

  1.   der Größe  , mit 0 als niedrigstem Index; speichert die Buckets
  2.   der Größe  , mit 0 als niedrigstem Index; speichert die (unteren) Schranken der Buckets
  3.  , hält für jedes Element   im Heap den Bucket, in dem es gespeichert ist

 

In der obigen Skizze ist die Datenstruktur noch einmal skizziert. Zu beachten ist nun, dass stets die folgenden Invarianten gelten müssen:

  1.   Schlüssel in  : die Schlüssel in   sind nach oben bzw. unten durch die Werte in   bzw.   beschränkt.
  2.   und   für  : 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  , der maximalen Differenz zweier Schlüsselwerte.

Operationen

Bearbeiten

Während der Initialisierung werden leere Buckets erzeugt und die unteren Schranken   berechnet (gemäß der Invariante 2); Laufzeit  .

Beim insert eines neuen Elements   wird linear von rechts nach links durch die Buckets gegangen und das neue Element mit   wird in den linkesten Bucket gespeichert, so dass gilt:  . Laufzeit  .

Bei decreaseKey wird nun das Feld   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   (amortisiert).

Die Operation extractMin gibt ein Element aus dem Bucket   zurück und entfernt es. Ist der Bucket   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   ausfindig gemacht und   auf k gesetzt (hierfür wird die Monotonie benötigt). Dann werden gemäß der Invarianten die Bucketgrenzen neu bestimmt und die Elemente aus   auf die neu entstandenen Buckets aufgeteilt; Laufzeit   (amortisiert).

Wenn jeweils angezeigt, dann muss zusätzlich das Feld   aktualisiert werden.

Literatur

Bearbeiten