next up previous contents
Nächste Seite: Union-Find-Datenstrukturen Aufwärts: Prioritätswarteschlangen Vorherige Seite: -level Buckets   Inhalt

Radix Heaps

Annahmen: wie k-level-Buckets

Definition: Ein Radix Heap besteht aus einem Array von $ ceil(\log(C+1))+1$ Buckets mit exponentiell zunehmender Größe der Schlüsselbereiche, deren Grenzen $ u$ nach folgende Invarianten erfüllen:
- Schlüssel im Bucket $ b[i]$ liegen innerhalb der Grenzen $ u[i]$ und $ u[i+1]$
- $ u[1]=u[0]+1$, sonst $ 0 \leq u[i+1]-u[i] \leq 2^{i-1}$

Operationen:

1. $ Insert$: lineare Suche nach Bucket, Start bei Bucket mit größtem Schlüsselbereich, amortisierte Kosten $ O(\log C)$
Begründung: jedes Element wird $ \leq \log C$ mal neu einsortiert und das nächste Minimum ist $ \leq \log C$ Buckets entfernt

2. $ ExtractMin$: Element des vordersten Buckets ausgeben und falls leer, Grenzen gemäß Invarianten(!) neu setzen, amortisierte Kosten $ O(1)$

3. $ DecreaseKey$: vom Bucket des Elements aus nach links neues Bucket suchen, amortisierte Kosten $ O(1)$



2003-10-08