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.

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]= 
  • 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

Bearbeiten

Sei  , die Schlüsselmenge  .

  • Dann ist T.size 
  • 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] .
  • T.p[2] zeigt auf   in T.list, T.p[3] auf   usw.

Für T.top und T.bottom müssen die Binärwerte der gespeicherten Zahlen betrachtet werden.  ,  ,  ,  ,  .

  • T.top ist 2-Struktur für die Werte  .
  • T.bottom hat 4 Einträge (jeweils einen für jedes Element aus T.top) mit
    • T.bottom[0]  ,
    • T.bottom[1]  ,
    • T.bottom[2]  ,
    • T.bottom[3]  .

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

Literatur

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