„Wer zuerst kommt, mahlt zuerst.“ Dieses Prinzip haben wir bei Schlangen kennen gelernt. In einer gewöhnlichen Schlange sind Dinge nach dem Zeitpunkt ihrer Aufnahme geordnet abgespeichert und werden in dieser Reihenfolge auch wieder daraus entnommen (FIFO-Prinzip). Oft will man Dinge aber nach einer anderen Priorität als dem Eintrittszeitpunkt geordnet abspeichern und gemäß dieser Priorität wieder entnehmen. Dabei kann es durchaus sein, dass zwischen zwei Dingen mit unterschiedlichen Prioritäten p1 und p2 ein neues Ding mit einer dazwischen liegenden Priorität p' eingefügt werden muss - im Gegensatz zu einer gewöhnlichen Schlange, bei der Einfügungen immer nur am Ende vorgenommen werden können.

So gibt es z. B. im täglichen Leben sehr dringende, dringende und weniger dringende Aufgaben, die in der Reihenfolge ihrer Dringlichkeit (Priorität) erledigt werden müssen. Die jeweils dringendste Aufgabe soll dabei immer als nächstes erledigt werden. Das Erledigen einer Aufgabe kann neue, zu erledigende Aufgaben mit eigenen Prioritäten nach sich ziehen. Durchaus kann sich die Priorität einer Aufgabe auch ändern, bevor die Aufgabe erledigt wurde, wenn diese aufgrund äußerer Umstände plötzlich als wichtiger oder weniger wichtiger eingestuft wird.

Was zur Modellierug solcher Problemstellungen benötigt wird, ist eine Prioritäts-Warteschlange (priority queue). Das ist eine Datenstruktur, die es erlaubt, Informationen nach einer bestimmten Priorität geordnet abzuspeichern und immer diejenige Information zu entnehmen, die gerade die geringste Priorität hat.

Warnung

Nach der klassischen Definition einer Prioritäts-Warteschlange, der auch die entsprechenden Typen von LEDA folgen, gelten die Informationen mit dem niedrigsten Prioritäts-Wert als die wichtigsten. Je kleiner der Wert, desto höher also die (umgangssprachliche) Priorität einer Information. Daher wird auch immer die Information mit dem geringsten Prioritäts-Wert als nächste entnommen, nicht die mit dem höchsten!

Die klassische Definition sieht darüber hinaus vor, dass die Priorität einer Information auf einen beliebigen Wert herabgesetzt werden kann.^[37]

Ein anschauliches Beispiel für eine Prioritäts-Warteschlange ist die Notaufnahme in einem großen Krankenhaus: Kommt ein neuer Patient an, wird die Schwere seiner Verletzung oder Krankheit geschätzt; gemäß dieser wird er in eine Prioritäts-Warteschlange eingeordnet. (Bei Verwendung einer klassischen Prioritäts-Warteschlange ist dabei der Prioritäts-Wert umso kleiner, je schwerer die Verletzung oder die Krankheit ist.) Der schlimmste Fall, etwa ein Herzinfarkt, wird immer als nächstes behandelt. Nun kann aber die Behandlung eines Falles neue Fälle erzeugen: Dem Herzinfarkt-Patienten kann während der Behandlung aus Versehen eine Spritze ins Auge gerammt worden sein, was dann zwar immer noch dringend zu behandeln, aber nicht mehr lebensgefährlich ist. Und das hohe Fieber des Patienten, der gerade von einer Tropenreise heimgekehrt ist, kann plötzlich zurückgehen: Dadurch sinkt die Priorität seines Falles. (Bei einer klassischen Prioritäts-Warteschlange bedeutet dies, dass der entsprechende Prioritäts-Wert erhöht wird.) In Wirklichkeit haben natürlich die Privatpatienten immer den niedrigsten Prioritäts-Wert.

Prioritäts-Warteschlangen sind eine wichtige algorithmische Zutat bei diskreten Ereignis-Simulationen (discrete event simulation): Ereignisse sollen behandelt werden, deren Zeitpunkte, eingetragen auf der Zeitachse, kein einfaches Muster aufweisen, so dass die Ereigniszeitpunke nicht durch eine einfache Schleife erzeugt werden können. Man kann hier das Verwalten der Zeitpunkte nicht so implementieren, wie wir das in unserer Simulation der Warteschlangen am Saarbrücker Hauptbahnhof getan haben. Dort laufen wir einfach durch alle Minuten eines Jahres, was deshalb nicht uneffizient ist, weil durchschnittlich in jeder Minute tatsächlich einige Ereignisse eintreten. Es gibt dort aber keine explizite Verwaltung der Zeitpunkte: Die for-Schleife läuft von selbst durch alle Zeitpunkte des Betrachtungszeitraums. Würden die Ereignisse aber nur alle paar Stunden und dies zudem noch unregelmäßig eintreten, so wäre diese Art der Simulation eine Verschwendung von Rechenzeit, weil nur in den seltensten Schleifendurchläufen wirklich ein Ereignis eintreten würde und behandelt werden müsste. Hier wäre es von Vorteil, die Ereignisse nach ihren Zeitpunkten geordnet in einer Prioritäts-Warteschlange zu verwalten, wobei die Prioritäten den Zeitpunkten entsprechen, und durch sukzessive Entnahme des Ereignisses mit der jeweils geringsten Priorität immer nur von Ereigniszeitpunkt zu Ereigniszeitpunkt zu springen.

Andere, typische Anwendungsgebiete von Prioritäts-Warteschlangen sind Algorithmen zur Berechnung kürzester Wege in Graphen (bei denen die Kanten eine Längeninformation tragen), Algorithmen zur Berechnung von maximalen Flüssen in Netzwerk-Graphen (bei denen die Kanten eine Kapazitätsinformation tragen), Kodierungs- und Kompressionsalgorithmen und Algorithmen für Branch-And-Bound zum Lösen von Optimierungsproblemen.

LEDA bietet für Problemstellungen dieser Art die Klassen p_queue und b_priority_queue an. Erstere implementiert Prioritäts-Warteschlangen für Informationen mit beliebigem Prioritäts-Typ. (Dieser muss natürlich ein linear geordneter Typ sein.) Letztere bietet eine besonders effiziente Implementierung für Prioritäten, von denen im Voraus bekannt ist, dass sie ganzzahlig sind und aus einem nicht allzu großen Intervall stammen.