imported>Thomas Dresler: Kommasetzung

2024-05-09T16:20:44Z

Kommasetzung

Neue Seite

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 ==
# alle Schlüssel sind aus den [[Natürliche Zahl|natürlichen Zahlen]]
# max. Schlüssel – min. Schlüssel <math>\le</math> C für ein festes C
# Monotonie von [[Vorrangwarteschlange#Operationen|''extractMin'']], d. h. die von aufeinander folgenden ''extractMin''-Aufrufen zurückgegebenen Werte sind [[Monoton steigende Funktion|monoton steigend]].

== Beschreibung der Datenstruktur ==
Die drei wichtigsten [[Feld (Datentyp)|Felder]] sind:
# <math>b</math> der Größe <math>B := \lfloor \log(C+1)\rfloor + 1</math>, mit 0 als niedrigstem Index; speichert die Buckets
# <math>u</math> der Größe <math>B+1</math>, mit 0 als niedrigstem Index; speichert die (unteren) Schranken der Buckets
# <math>bNum</math>, hält für jedes Element <math>x</math> im Heap den Bucket, in dem es gespeichert ist

[[Bild:RadixHeap1.png]]

In der obigen Skizze ist die Datenstruktur noch einmal skizziert. Zu beachten ist nun, dass stets die folgenden [[Invariante (Informatik)|Invarianten]] gelten müssen:
# <math>u[i] \le</math> Schlüssel in <math>b[i] < u[i+1]</math>: die Schlüssel in <math>b[i]</math> sind nach oben bzw. unten durch die Werte in <math>u[i+1]</math> bzw. <math>u[i]</math> beschränkt.
# <math>u[0] = 0, u[1] = u[0] + 1, u[B] = \infty</math> und <math>0 \le u[i+1]-u[i] \le 2^{i-1}</math> für <math>i = 1, \ldots, B-1</math>: 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 <math>C</math>, der maximalen Differenz zweier Schlüsselwerte.

== Operationen ==
Während der ''Initialisierung'' werden leere Buckets erzeugt und die unteren Schranken <math>u</math> berechnet (gemäß der Invariante 2); Laufzeit <math>O(B)</math>.

Beim ''insert'' eines neuen Elements <math>x</math> wird linear von rechts nach links durch die Buckets gegangen und das neue Element mit <math>k(x)</math> wird in den linkesten Bucket gespeichert, so dass gilt: <math>u[i] \ge k(x)</math>. Laufzeit <math>O(B)</math>.

Bei ''decreaseKey'' wird nun das Feld <math>bNum</math> benötigt. Von dem nun bekannten Bucket aus wird analog zur Operation ''insert'' nun nach der [[Inkrement und Dekrement|Dekrementierung]] des Schlüsselwertes nach links iteriert (es muss zusätzlich auf Einhaltung der Invarianten geprüft werden); Laufzeit <math>O(1)</math> (amortisiert).

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

Wenn jeweils angezeigt, dann muss zusätzlich das Feld <math>bNum</math> aktualisiert werden.

== Literatur ==
* B.V. Cherkassky, A.V. Goldberg, C. Silverstein: [http://xenon.stanford.edu/~csilvers/papers/hotq-soda.ps ''Buckets, Heaps, Lists and Monotone Priority Queues''] ([http://xenon.stanford.edu/~csilvers/papers/hotq-soda-abstract.txt Abstract]), in: Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms. Januar 1997, S. 83–92.

[[Kategorie:Datenstruktur]]

Radix Heap - Versionsgeschichte

imported>Thomas Dresler: Kommasetzung