Van-Emde-Boas Vorrangwarteschlange

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 aller möglich 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]=$\begin{cases} 1 & i \in T.list\\0 & sonst\\\end{cases}$
• 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 k = 4, die Schlüsselmenge S = {2,3,7,10,13}.

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

Für T.top und T.bottom müssen die Binärwerte der gespeicherten Zahlen betrachtet werden. 2₁₀ = 0010₂, 3₁₀ = 0011₂, 7₁₀ = 0111₂, 10₁₀ = 1010₂, 13₁₀ = 1101₂.

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

Ein Schlüssel x mit x > = 16 kann in dieser 4-Struktur nicht gespeichert werden, da 2⁴ = 16 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.