Vorrangwarteschlange - LinkFang.de





Vorrangwarteschlange


In der Informatik ist eine Vorrangwarteschlange (auch Prioritätenliste, Prioritätsschlange, Prioritätswarteschlange oder englisch 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.

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 Zeit-Ereignis-Paar in die Vorrangwarteschlange eingefügt und die Vorrangwarteschlange gibt dann das jeweils aktuelle (d. h. als nächstes zu verarbeitende) Ereignis aus.

Gierige Algorithmen machen ebenfalls von Prioritätswarteschlangen Gebrauch, da dort häufig das Minimum oder Maximum einer Menge bestimmt werden muss. Einer der bekanntesten Algorithmen dieser Art ist der Algorithmus von Dijkstra zur Berechnung kürzester Wege.

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.

Literatur

  • George F. Luger: Künstliche Intelligenz. Strategien zur Lösung komplexer Probleme. 2001, ISBN 3-8273-7002-7

Weblinks


Kategorien: Datenstruktur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Vorrangwarteschlange (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.