Prioritätswarteschlangen

Definition:
Eine Prioritätswarteschlange (Priority Queue) ist eine Datenstruktur mit eindeutigen Schlüsselwerten zu den Daten. Sie stellt die Operationen Insert, ExtractMin (Minimum lesen und löschen) sowie DecreaseKey (Schlüssel erniedrigen) zur Verfügung, häufig auch ein explizites Delete.

Bemerkungen:
- DecreaseKey lässt sich immer durch die Sequenz Delete und Insert realisieren.
- DecreaseKey und Delete wird eine Referenz auf das Element in der Warteschlange übergeben, da sonst die explizite Suche nach dem Element lineare Zeit kosten kann.