Von-Ende-Boas-PQ

Von Ende Boas, P., R. Kaas, E.Zijlstra:
Universum $U,\ \vert U\vert=N,\ U \subseteq \mathbbm{N}$
Hier: $U=\{0,1,\ldots,N-1\}$
Bessere Priority-Queue für den Fall $n \geq \log N$

Sei $k \in \mathbbm{N},\ k \geq 2;\ k'=\left\lceil \frac{k}{2} \right\rceil,\ k''=\left\lfloor\frac{k}{2} \right\rfloor$
$x \in [0,\ldots,2^k-1] \leq k$ Bits
$x'=\left\lfloor\frac{x}{2^{k''}} \right\rfloor, x'' := x \mod 2^{k''}$ (x' vordere Hälfte, x'' hintere Hälfte der Bits)
Sei $S=\{x_1,\ldots,x_m\} \subseteq [0,\ldots,2^k-1]$

Definition: Eine k-Struktur T für S besteht aus:

1.

der Zahl $\text{T.size}=\vert\{x_1,\ldots,x_m\}\vert=\vert S\vert=m$

2.

einer doppelt verketteten Liste T.list, die die Elemente von S in aufsteigender Reihenfolge enthält

3.

einem Bitvektor $\text{T.b}[0 \ldots 2^k-1]$ mit $\text{T.b}[i]=\genfrac{}{}{0pt}{}{0}{1}$ falls $\genfrac{}{}{0pt}{}{i \not\in S}{i \in S}$ einem Zeiger (Pointer) Vektor $\text{T.p}[0 \ldots 2^k-1]$. Falls $\text{T.b}[i]=1$, dann zeigt $\text{T.p}[i]$ auf i in der Liste aus 2.

4.

einer k'-Struktur T.top und einem Feld $\text{T.bottom}[0 \ldots 2^{k`}-1]$ von k''-Strukturen. Falls m=1, dann T.top, T.bottom und die zugehörigen k''-Strukturen leer, $\text{T.size}=1$. $\text{T.list}=\{x\}$, der Bitvektor wird nicht benötigt. Falls m>1, dann ist T.top eine k'-Struktur für die durch $\{x_1', x_2', \ldots, x_m'\}$ gegebene Menge, und für jedes $x \in [0 \ldots 2^{k'}-1]$ ist $\text{T.bottom}[x]$ eine k''-Struktur für die Menge $\{x_i'';\ 1 \leq i \leq m;\ x=x_i'\}$

Beispiel:
$k=4,\ S=\{2,3,7,10,13\},\ \text{T.size}=5$

T.top ist 2-Struktur $\{0,1,2,3\}$
$\text{T.bottom}[0]$ ist eine 2-Struktur für $\{2,3\}$
$\text{T.bottom}[1]$ ist eine 2-Struktur für $\{3\}$
$\text{T.bottom}[2]$ ist eine 2-Struktur für $\{2\}$
$\text{T.bottom}[3]$ ist eine 2-Struktur für $\{1\}$
Operation Succ(x) findet $\min\{y \in \text{S};\ y \gt x\}$ in der k-Struktur T.

if k=1 or $\text{T.Size} \leq 2$ then
		naive Suche
else
		if $\text{T.size}=0$ or $x \geq \max \text{in T.list}$ then
				return(   Succ(x) gibt's nicht)
		else
				$x':=\left\lfloor\frac{x}{2^{k''}} \right\rfloor$;  				$x'':= x \mod 2^{k''}$;  				if $\text{T.top.b}[x']=1$ and $x'' < \max\{\text{T.bottom}[x']\}$ then
						return($x' \cdot 2^{k''}$+    Succ($x'', \text{T.bottom}[x']$)
				else
						z':=   Succ($x', \text{T.top})$, return($z' \cdot 2^{k''} + \min\{\text{T.bottom}[z']\}$)				fi
		fi
fi

Kosten: $\text{T}(k) \leq c + \text{T}(\left\lceil \frac{k}{2} \right\rceil)=\mathcal{O}(\log k)$

Lemma: Die Succ -Operation hat Zeitbedarf $\mathcal{O}(\log k)$

Beweis: $\surd$ $\Diamond$

Insert Operation:

• falls x bereits in Priority-Queue, dann fertig
• bestimme Succ($x, \text{T})$ , füge x davor ein
• bestimme x' und x''
• behandle die entsprechende Unterstrukturen rekursiv:
  

  Insert(x',T.top) , Insert(x'',T.bottom[x']) (nur ein nicht trivialer rekursiver Aufruf)

Zeitbedarf: naiv $\mathcal{O}(\log^2k)$, Optimierung: das oberste Succ tut alles $\mathcal{O}(\log k)$

Delete Operation:

Komplexität von Delete in k-Struktur: $\mathcal{O}(\log k)$
Kosten der Initialisierung: $\sim$ Größe der Datenstruktur
Platzbedarf für k-Struktur: Sei S(k) der Platzbedarf für eine k-Struktur.
Dann gilt:
S(1)=c
S$(k)=c2^k+\text{S}(k')+2^{k'}\text{S}(k')$ für $k \geq 2$
Wir ersetzen zur Vereinfachung: S$(k)=c2^k+\text{S}(\frac{k}{2})+2^{\frac{k}{2}}\text{S}(\frac{k}{2})$

Lemma: S$(k) = \mathcal{O}(2^k \cdot \log k)$

Beweis:
Setze: S$(k):= c' \cdot 2^k \log k$ (besser: Zeige S$(k):= c' 2^k \log k$ funktioniert)
Für k=1 klar
Rekursionsschritt:

$$\begin{split} \text{Platz f\uml {u}r}\ k\text{-Struktur} &\... ... f\uml {u}r } c' \text{ gro\ss{} genug.)} \quad\quad\end{split}$$

$\Diamond$



Beweis: s.o. $\Diamond$

Literatur zu van Emde Boas-Priority Queue:

1.

Mehlhorn Bd. 1, S.290-296

2.

van Emde Boas, P., R. Kaas, E. Zijlstra: Design and Implementation of an efficient priority queue, Math. Systems Theory 10 (1977), S. 99-127