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]=${\displaystyle {\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 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 ${\displaystyle k=4}$, die Schlüsselmenge ${\displaystyle S=\{2,3,7,10,13\}}$.

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

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

• T.top ist 2-Struktur für die Werte ${\displaystyle \{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] ${\displaystyle =\{10_{2},11_{2}\}=\{2,3\}}$,
  • T.bottom[1] ${\displaystyle =\{11_{2}\}=\{3\}}$,
  • T.bottom[2] ${\displaystyle =\{10_{2}\}=\{2\}}$,
  • T.bottom[3] ${\displaystyle =\{01_{2}\}=\{1\}}$.

Ein Schlüssel ${\displaystyle x}$ mit ${\displaystyle x>=16}$ kann in dieser 4-Struktur nicht gespeichert werden, da ${\displaystyle 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.