$k$-level Buckets

Annahmen:
- Schlüssel sind ganzzahlig
- Es gilt stets: $maxKey - minKey \leq C$

Definition:
Ein Bucket ist eine Liste zur Aufnahme von Elementen eines festen Schlüssels oder eines Bereichs von Schlüsseln.

Definition:
Die 1-level-Buckets bestehen aus
- einem Array der Länge $C+1$ von Buckets mit festem Schlüssel,
- einer Zahl $minvalue$, dem kleinsten gespeicherten Schlüssel,
- einer Zahl $minpos$, der korresponierenden Bucketnummer.

Operationen:

1. $Insert$: in Bucket $key(x) \>mod\> C+1$, Kosten $O(1)$

2. $ExtractMin$: $minvalue$ ausgeben und nächste $minvalue$ und $minpos$ ermitteln, Kosten $O(C)$

3. $Delete$: Element aus Bucket löschen, Kosten $O(1)$

Definition: Die k-level-Buckets bestehen aus $k$ 1-level-Buckets der Länge $floor((C+1)^{1/k})+1$ zum Vorhalten der Werte mit Buckets von festem Schlüssel in den untersten 1-level-Buckets. Die darüber liegenden Schichten enthalten ganze Bereiche von Schlüsseln pro Bucket.

Operationen:
Alle Operationen werden nun in ihrer Implementierung komplexer. Bei $ExtractMin$ entsteht bei neuem $minpos$ der Overhead, das vorderste Bucket mit den Werten aus darüber liegenden Schichten zu füllen, was im Extremfall zur Komplexität $O(C^{1/k} + n)$ führt. Die amortisierte Analyse zeigt jedoch für $ExtractMin$ Kosten von $O(C^{1/k})$.