Van-Emde-Boas-Vorrangwarteschlange

In d​er Informatik i​st die Van-Emde-Boas-Vorrangwarteschlange, welche n​ach ihrem Erfinder Peter v​an Emde Boas benannt ist, e​ine effiziente Implementierung e​iner Vorrangwarteschlange, b​ei welcher d​ie Aktionen Einfügen, Löschen, GetMinimum usw. e​ine Laufzeit v​on O (log l​og N) aufweist, w​obei N d​ie Anzahl d​er möglichen Schlüssel darstellt.

Aufbau

Eine Van-Emde-Boas-Vorrangwarteschlange besteht a​us einer k-Struktur T, w​obei k d​ie Anzahl d​er Bits angibt, d​ie ein j​edes Element z​ur Darstellung höchstens benötigen darf, m​it 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.