2-Level-Buckets

Bei einem großen Wertebereich der zu speichernden Schlüssel, das heißt beim großen C, und einer geringen Anzahl tatsächlich abgelegter Datenelemente sind 1-Level-Buckets in zweifacher Hinsicht ungünstig:

• Das Array b belegt statisch Speicherplatz der Größe $\mathcal{O}(C)$, obwohl nur ein kleiner Teil davon wirklich gebraucht wird.
• Der Zeitbedarf für ein ExtractMin nähert sich der worst-case-Komplexität $\mathcal{O}(C)$,da der nächste nicht-leere Bucket ziemlich weit entfernt sein kann.

2-Level-Buckets versuchen dem mit folgender Idee abzuhelfen: Verwende statt eines Arrays der Länge C+1 zwei Arrays der Länge:

$$B = \vert\sqrt{C+1}\vert+1$$

Dabei enthält eines der beiden Arrays die meisten Elemente in grob vorsortierter Form, nur die Elemente mit den kleinsten Schlüsseln werden in dem zweiten Array dann endgültig sortiert vorgehalten. 2-Level-Buckets können mit folgenden Elementen aufgebaut werden:

• Das Array btop ([0..B-1]) nimmt in jedem Bucket Elemente mit Schlüsseln aus einem Intervall der Länge B auf; die Schlüssel stammen aus allen Intervallen außer dem niedrigsten Intervall.
• Das Array bbot ([0..B-1]) nimmt in jedem Bucket Elemente mit genau einem Schlüssel auf; die Schlüssel stammen nur aus dem niedrigsten.
• valtop ist die linke Intervallgrenze des niedrigsten Intervalls.
• postop enthält den Index des Buckets in btop für das niedrigste Intervall (das aber in bbot gespeichert wird).
• nbot ist die Anzahl der Elemente in bbot
• n ist die Anzahl der Elemente in bbot und btop

Dabei gilt:

• $btop[(postop+1) \text{ mod } B]$ enthält alle Elemente x mit:
  $valtop +iB \leq \text{Key}(x) < valtop +(i+1)B$, wobei $1 \leq i \leq B-1$
• bbot[i] enthält alle Elemente x mit
  Key(x) = valtop +i, wobei $0 \leq i \leq B-1$

Dazu ist allerdings folgende Annahme zu machen:
Hat ein ExtractMin ein Element mit Schlüssel k zurückgeliefert, werden bis zum nächsten Aufruf von ExtractMin nur Elemente mit Schlüsseln $\geq k$ und $\leq k+C$ eingefügt. Dies stellt sicher, daß ein Element aus bbot nie nach btop wandert.

Lemma: Zu jedem Zeitpunkt haben alle Schlüssel Platz in der Datenstruktur.

Beweis: Am meisten Platz wird benötigt, wenn der kleinste Schlüssel ganz rechts in bbot gespeichert oder dort entfernt worden ist. Er hat dann den Wert valtop + B -1. Der größte Schlüssel, der nun vorkommen kann und also Platz finden muß, ist valtop + B -1 +C:

$$\begin{split} & \ \ \text{Gr\uml {o}\ss{}tm\uml {o}glicher S... ...}\ss{}tm\uml {o}glicher erlaubter Schl\uml {u}ssel} \end{split}$$

$\Diamond$
Annahme: Vor dem ersten ExtractMin werden nur Elemente mit 0 $\leq$ Schlüssel $\leq$ C eingefügt.

i)

Initialize :

valtop = postop = nbot = n = 0;  
Initialisiere bbot, btop;  

ii)

Insert(x) :

überprüfe Invarianten;
$i:= \left( \lfloor \frac{\text{Key(x)}-valtop}{B} \rfloor + postop \right)$ mod B;
if i== postop then
		Füge x in bbot[Key(x)-valpop] ein;
		nbot:= nbot + 1 ; n:=n+1;
else
		Füge x in btop[i] ein;
fi  

iii)

ExtractMin

co suche kleinste Element in bbot oc
j:=0 ; while $bbot[j] ==\emptyset$ do j:=j+1 od
entferne ein (beliebiges) Element aus bbot[j] und gib es zurück;
nbot := nbot -1 ; n := n -1; 
if n==0 then return fi
if nbot==0 then
		 while $btop[postop]==\emptyset$ do
		 		 postop:=(postop+1) mod B;
		 		 valtop:=valtop + B;
		 od
		 while $btop[postop]\neq\emptyset$ do
		 		 entferne beliebiges Element x aus btop[postop];
		 		 Füge x im bbot[Key(x)-valtop] ein;
		 		 nbot:=nbot+1;
		 od
fi

iv)

DecreaseKey(x,k)

enferne x aus seinem momentanen Bucket;
falls nötig, aktualisiere nbot
Key(x) := k; 
Insert(x);  

Lemma: Worst-case (reelle) Laufzeit bei 2-Level Buckets sind für Insert und

DecreaseKey $\mathcal{O}(1)$, für ExtractMin

$\mathcal{O}(n+\sqrt{C})$ und $\mathcal{O}(\sqrt{C})$ (bzw. $\mathcal{O}(1)$) für Initialize .

Beweis:
- Insert : $\mathcal{O}(1)+1=\mathcal{O}(1)$
- DecreaseKey : $\mathcal{O}(1)+(\leq0)= \mathcal{O}(1)$
- ExtractMin $\mathcal{O}(\sqrt{C}+\sqrt{C}+$ # Elemente $\begin{array} {c}btop\\ \downarrow\\ bbot\end{array}$). $\Diamond$

Potential: Anzahl von Elementen im Buckets im btop.




Beweis:
- Insert : s.o.
- DecreaseKey : s.o.
- ExtractMin : $\mathcal{O}(\sqrt{C}+$ # Elemente $\begin{array} {c}btop\\ \downarrow\\ bbot \end{array})-$ # Elemente $\begin{array} {c}btop\\ \downarrow\\ bbot \end{array} = \mathcal{O}(\sqrt{C})$ $\Diamond$