Van-Emde-Boas-Vorrangwarteschlange

Vorlage:Überarbeiten 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

Eine Van-Emde-Boas-Vorrangwarteschlange 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{array}{cc}1& i\in T.list\\ 0& sonst\end{array}$
• 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 k/2-Strukturen, welche jeweils einen Eintrag enthalten für die Elemente von T.top, mit dem Inhalt der hinteren Hälfte der 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_{10}=0010_2$, $3_{10}=0011_2$, $7_{10}=0111_2$, $10_{10}=1010_2$, $13_{10}=1101_2$.

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

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

Literatur

• P. van Emde-Boas, R. Kass, 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, Juni 1977.