Annahmen: wie k-level-Buckets
Definition:
Ein Radix Heap besteht aus einem Array von
Buckets mit exponentiell zunehmender Größe der Schlüsselbereiche, deren Grenzen nach folgende Invarianten erfüllen:
- Schlüssel im Bucket liegen innerhalb der Grenzen und
-
, sonst
Operationen:
1. : lineare Suche nach Bucket, Start bei Bucket mit größtem Schlüsselbereich, amortisierte Kosten
Begründung: jedes Element wird
mal neu einsortiert und das nächste Minimum ist
Buckets entfernt
2. : Element des vordersten Buckets ausgeben und falls leer, Grenzen gemäß Invarianten(!) neu setzen, amortisierte Kosten
3. : vom Bucket des Elements aus nach links neues Bucket suchen, amortisierte Kosten