Buckets

Next: 1-Level-Backets Up: Radix-basierte Priority-Queue Previous: Radix-basierte Priority-Queue

Eine relativ einfache Möglichkeit, Vorrangwarteschlangen zu implementieren, stellen Buckets dar. Dazu müssen folgende Annahmen erfüllt sein:

Schlüssel sind ganzzahlig
Zu jedem Zeitpunkt gilt für die zu speichernden Elemente:
$\fbox {gr\uml {o}\ss{}ter Schl\uml {u}ssel - kleinster Schl\uml {u}ssel $\leq C$}$

Diese Bedingungen sind zum Beispiel beim Algorithmus von Dijkstra erfüllt. C ist hier gleich der maximalen Kantenlänge.

Abbas-Bardia Kabiri-Jarghouyeh
3/3/1999