Van-Emde-Boas-Vorrangwarteschlange - LinkFang.de





Van-Emde-Boas-Vorrangwarteschlange


Dieser Artikel oder Abschnitt bedarf einer Überarbeitung.

In der Informatik ist die Van-Emde-Boas-Vorrangwarteschlange, welche nach ihrem Erfinder Peter van Emde Boas benannt ist, eine effiziente Implementierung einer Vorrangwarteschlange, bei welcher die Aktionen Einfügen, Löschen, GetMinimum usw. eine Laufzeit von O(log log N) aufweist, wobei N die Anzahl der möglichen Schlüssel darstellt.

Aufbau

Sie besteht aus einer k-Struktur T, wobei k die Anzahl der Bits angibt, die ein jedes Element zur Darstellung höchstens benötigen darf, mit folgenden Eigenschaften:

  • T.size: Anzahl aller Elemente, welche in der Vorrangwarteschlange aktuell gespeichert sind
  • T.list: Doppelt verkettete Liste, die die gespeicherten Schlüssel in aufsteigender Reihenfolge enthält
  • T.b: Ein Bitvektor mit T.b[i]=[math]\begin{cases} 1 & i \in T.list\\0 & sonst\\\end{cases} [/math]
  • T.p: Ein Vektor von Zeigern auf die Elemente von T.list. Wenn T.b[i] = 1, dann zeigt T.p[i] auf i in T.list;
  • T.top: Die gleiche hier beschriebene k/2-Struktur, welche die vordere Hälfte der Bits aller in T.list enthaltenen Schlüssel enthält
  • T.bottom: Ein Feld mit von k/2-Strukturen, welche jeweils einen Eintrag enthält für die Elemente von T.top, mit dem Inhalt der hinteren Hälfte Bits, die zu der vorderen Hälfte zugehörig ist.

Beispiel

Sei [math]k=4[/math], die Schlüsselmenge [math]S=\{2,3,7,10,13\}[/math].

  • Dann ist T.size[math]=5[/math]
  • T.list enthält die Schlüssel aus S in aufsteigender Reihenfolge doppelt verkettet,
  • T.b[2][math]=[/math]T.b[3][math]=[/math]T.b[7][math]=[/math]T.b[10][math]=[/math]T.b[13][math]=1[/math].
  • T.p[2] zeigt auf [math]2[/math] in T.list, T.p[3] auf [math]3[/math] usw.

Für T.top und T.bottom müssen die Binärwerte der gespeicherten Zahlen betrachtet werden. [math]2_{10} = 0010_{2}[/math], [math]3_{10} = 0011_{2}[/math], [math]7_{10} = 0111_{2}[/math], [math]10_{10} = 1010_{2}[/math], [math]13_{10} = 1101_{2}[/math].

  • T.top ist 2-Struktur für die Werte [math]\{00_2, 01_2, 10_2, 11_2\} = \{0, 1, 2, 3\}[/math]
  • T.bottom hat 4 Einträge (jeweils einen für jedes Element aus T.top) mit
    • T.bottom[0] [math]= \{10_2, 11_2\} = \{2, 3\}[/math],
    • T.bottom[1] [math]= \{11_2\} = \{3\}[/math],
    • T.bottom[2] [math]= \{10_2\} = \{2\}[/math],
    • T.bottom[3] [math]= \{01_2\} = \{1\}[/math]

Ein Schlüssel [math]x[/math] mit [math]x\gt=16[/math] kann in dieser 4-Struktur nicht gespeichert werden, da [math]2^4=16[/math] und somit mehr als 4 Bits zur Speicherung nötig wären.

Literatur und Quellen

  • P. van Emde-Boas, R. Kass und E. Zijlstra: Design and Implementation of an Efficient Priority Queue. In: Mathematical Systems Theory. 10: 99–127, 1977.
  • P. van Emde-Boas: Preserving Order in a Forest in Less than Logarithmic Time and Linear Space. In: Inf. Proc. Letters. 6(3): 80–82, June 1977.

Kategorien: Datenstruktur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Van-Emde-Boas-Vorrangwarteschlange (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.