Van-Emde-Boas-Vorrangwarteschlange
# 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 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{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 $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.

