Van-Emde-Boas-Vorrangwarteschlange

Vorlage:Hinweisbaustein 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]=<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 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 <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>=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

• 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.