Prioritätswarteschlange

Prioritätswarteschlange

In der Informatik ist eine Vorrangwarteschlange (auch Prioritätswarteschlange oder engl. priority queue genannt) eine spezielle abstrakte Datenstruktur, genauer eine erweiterte Form einer Warteschlange. Den Elementen, die in die Warteschlange gelegt werden, wird ein Schlüssel mitgegeben, der die Reihenfolge der Abarbeitung der Elemente bestimmt.

Inhaltsverzeichnis

Operationen

Vorrangwarteschlangen müssen die Operationen

  • insert, zum Einfügen eines Elementes und
  • extractMin, zur Rückgabe und zum Entfernen des Elements mit dem kleinsten Schlüssel (= höchster Priorität)

unterstützen.

Daneben gibt es noch Operationen, die vor allem für Online-Algorithmen wichtig sind:

  • remove entfernen eines Elements
  • decreaseKey den Schlüsselwert verringern (=die Priorität erhöhen)

Implementierung

Die Implementierung von Vorrangwarteschlangen kann über AVL-Bäume erfolgen. Sowohl insert als auch extractMin können dann in O(log n) Zeit ausgeführt werden. Eine andere Möglichkeit besteht in der Verwendung partiell geordneter Bäume (Heaps). Auch hier liegt die Zeitkomplexität bei O(log n).

Beispiele für Datenstrukturen, die Vorrangwarteschlangen effizient implementieren sind

Anwendungen

Prioritätswarteschlangen können für die Implementierung diskreter Ereignissimulationen genutzt werden. Dabei werden zu den jeweiligen Ereignissen als Schlüssel die Zeiten berechnet, das Ereignis-Zeit-Paar in die Vorrangwarteschlange eingefügt und die Vorrangwarteschlange gibt dann das jeweils aktuelle (d.h. als nächstes zu verarbeitende) Ereignis aus.

Greedy-Algorithmen machen ebenfalls von Prioritätswarteschlangen Gebrauch, da dort häufig das Minimum, bzw. Maximum, einer Menge bestimmt werden muss.

Erweiterungen

Neben der klassischen, einendigen Vorrangwarteschlange existieren auch zweiendige. Diese unterstützen zusätzlich eine Operation extractMax, um das Element mit dem größten Schlüssel herauszuziehen. Eine Möglichkeit für die Implementierung solcher Datenstrukturen bieten Doppelheaps. Alternativ können auch Datenstrukturen wie Min-Max-Heaps genutzt werden, die direkt zweiendige Prioritätswarteschlangen unterstützen.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Jarnik, Prim und Dijkstra — Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 von dem tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er …   Deutsch Wikipedia

  • Dijkstra-Algorithmus — Animation des Dijkstra Algorithmus Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger W. Dijkstra) ist ein Algorithmus aus der Klasse der Greedy Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Er… …   Deutsch Wikipedia

  • Prim-Dijkstra-Algorithmus — Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 von dem tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er …   Deutsch Wikipedia

  • Primscher Algorithmus — Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 von dem tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er …   Deutsch Wikipedia

  • A* — Der A* Algorithmus („A Stern“ oder englisch „a star“) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er… …   Deutsch Wikipedia

  • A-Stern-Algorithmus — Der A* Algorithmus („A Stern“ oder englisch „a star“) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er… …   Deutsch Wikipedia

  • A Stern — Der A* Algorithmus („A Stern“ oder englisch „a star“) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er… …   Deutsch Wikipedia

  • A star — Der A* Algorithmus („A Stern“ oder englisch „a star“) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er… …   Deutsch Wikipedia

  • Algorithmus von Prim — Der Algorithmus von Prim dient der Berechnung eines minimalen Spannbaumes in einem zusammenhängenden, ungerichteten, kantengewichteten Graphen. Der Algorithmus wurde 1930 vom tschechischen Mathematiker Vojtěch Jarník entwickelt. 1957 wurde er… …   Deutsch Wikipedia

  • GDUS — Der A* Algorithmus („A Stern“ oder englisch „a star“) gehört zur Klasse der informierten Suchalgorithmen. Er dient in der Informatik der Berechnung eines kürzesten Pfades zwischen zwei Knoten in einem Graphen mit positiven Kantengewichten. Er… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”