www.wikidata.de-de.nina.az

Radix Heap Ein ist eine Datenstruktur zur Realisation der Operationen einer Vorrangwarteschlange Hiermit kann dann eine

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 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

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Ein Radix Heap ist eine Datenstruktur zur Realisation der Operationen einer Vorrangwarteschlange Hiermit kann dann eine Menge von Elementen denen jeweils ein Schlussel zugeordnet ist verwaltet werden Die Laufzeit der Operationen ist abhangig von der Differenz des grossten und kleinsten Schlussels bzw konstant Die Datenstruktur besteht hauptsachlich aus einer Reihe von Buckets von engl bucket Eimer deren Grosse exponentiell zunimmt Inhaltsverzeichnis 1 Voraussetzungen 2 Beschreibung der Datenstruktur 3 Operationen 4 LiteraturVoraussetzungen Bearbeitenalle Schlussel sind aus den naturlichen Zahlen max Schlussel min Schlussel displaystyle leq nbsp C fur ein festes C Monotonie von extractMin d h die von aufeinander folgenden extractMin Aufrufen zuruckgegebenen Werte sind monoton steigend Beschreibung der Datenstruktur BearbeitenDie drei wichtigsten Felder sind b displaystyle b nbsp der Grosse B log C 1 1 displaystyle B lfloor log C 1 rfloor 1 nbsp mit 0 als niedrigstem Index speichert die Buckets u displaystyle u nbsp der Grosse B 1 displaystyle B 1 nbsp mit 0 als niedrigstem Index speichert die unteren Schranken der Buckets b N u m displaystyle bNum nbsp halt fur jedes Element x displaystyle x nbsp im Heap den Bucket in dem es gespeichert ist nbsp In der obigen Skizze ist die Datenstruktur noch einmal skizziert Zu beachten ist nun dass stets die folgenden Invarianten gelten mussen u i displaystyle u i leq nbsp Schlussel in b i lt u i 1 displaystyle b i lt u i 1 nbsp die Schlussel in b i displaystyle b i nbsp sind nach oben bzw unten durch die Werte in u i 1 displaystyle u i 1 nbsp bzw u i displaystyle u i nbsp beschrankt u 0 0 u 1 u 0 1 u B displaystyle u 0 0 u 1 u 0 1 u B infty nbsp und 0 u i 1 u i 2 i 1 displaystyle 0 leq u i 1 u i leq 2 i 1 nbsp fur i 1 B 1 displaystyle i 1 ldots B 1 nbsp die Grossen 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 Abhangigkeit der Feldgrossen zum Wert C displaystyle C nbsp der maximalen Differenz zweier Schlusselwerte Operationen BearbeitenWahrend der Initialisierung werden leere Buckets erzeugt und die unteren Schranken u displaystyle u nbsp berechnet gemass der Invariante 2 Laufzeit O B displaystyle O B nbsp Beim insert eines neuen Elements x displaystyle x nbsp wird linear von rechts nach links durch die Buckets gegangen und das neue Element mit k x displaystyle k x nbsp wird in den linkesten Bucket gespeichert so dass gilt u i k x displaystyle u i geq k x nbsp Laufzeit O B displaystyle O B nbsp Bei decreaseKey wird nun das Feld b N u m displaystyle bNum nbsp benotigt Von dem nun bekannten Bucket aus wird analog zur Operation insert nun nach der Dekrementierung des Schlusselwertes nach links iteriert es muss zusatzlich auf Einhaltung der Invarianten gepruft werden Laufzeit O 1 displaystyle O 1 nbsp amortisiert Die Operation extractMin gibt ein Element aus dem Bucket b 0 displaystyle b 0 nbsp zuruck und entfernt es Ist der Bucket b 0 displaystyle b 0 nbsp noch nicht leer so ist die Operation beendet Ist er jedoch nun leer so wird der nachstgrossere nicht leere Bucket gesucht dessen kleinstes Element k displaystyle k nbsp ausfindig gemacht und u 0 displaystyle u 0 nbsp auf k gesetzt hierfur wird die Monotonie benotigt Dann werden gemass der Invarianten die Bucketgrenzen neu bestimmt und die Elemente aus b i displaystyle b i nbsp auf die neu entstandenen Buckets aufgeteilt Laufzeit O 1 displaystyle O 1 nbsp amortisiert Wenn jeweils angezeigt dann muss zusatzlich das Feld b N u m displaystyle bNum nbsp aktualisiert werden Literatur BearbeitenB 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 Abgerufen von https de wikipedia org w index php title Radix Heap amp oldid 197928332