Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


11. Prioritätswarteschlangen



In vielen Anwendungen müssen Datensätze mit Schlüsseln der Reihe nach verarbeitet werden, doch nicht unbedingt in einer vollständig sortierten Reihenfolge und nicht unbedingt alle auf einmal. Oft muß eine Menge von Datensätzen gesammelt und dann der größte verarbeitet werden, wonach vielleicht weitere Datensätze gesammelt werden und dann der nächstgrößte verarbeitet wird usw. Eine geeignete Datenstruktur muß unter solchen Bedingungen die Eigenschaft haben, daß sie die Operationen des Einfügens eines neuen Elementes und des Löschens des größten Elementes unterstützt. Eine derartige Datenstruktur, die Schlangen (Löschen des ältesten Elements) und Stapeln (Löschen des neuesten Elements) gegenübergestellt werden kann, wird Prioritätswarteschlange (priority queue) genannt. Tatsächlich kann man sich die Prioritätswarteschlange als eine Verallgemeinerung des Stapels und der Schlange (und anderer einfacher Datenstrukturen) vorstellen, da diese Datenstrukturen durch Verwendung geeigneter Prioritätszuweisungen mit Prioritätswarteschlangen implementiert werden können.

Zu den Anwendungen von Prioritätswarteschlangen gehören Simulationssysteme (wo die Schlüssel den »Ereigniszeiten« entsprechen könnten, die der Reihe nach verarbeitet werden müssen), das Job-Scheduling in Computersystemen (wo die Schlüssel den »Prioritäten« entsprechen könnten, die angeben, welche Benutzer zuerst bedient werden) und numerische Berechnungen (wo die Schlüssel Berechnungsfehler sein könnten, so daß der größte zuerst bearbeitet werden kann).

Später im Buch werden wir sehen, wie Prioritätswarteschlangen als elementare Bausteine für weiterentwickelte Algorithmen benutzt werden können. In Kapitel 22 entwickeln wir unter Verwendung von Routinen aus diesem Kapitel einen Algorithmus zur Verdichtung von Dateien, und in den Kapiteln 31 und 33 werden wir sehen, wie Prioritätswarteschlangen als Basis für verschiedene fundamentale Algorithmen zum Durchsuchen von Graphen dienen können. Dies sind nur einige wenige Beispiele für die wichtige Rolle, die die Prioritätswarteschlange als grundlegendes Werkzeug für die Entwicklung von Algorithmen spielt.

Es ist nützlich, die Handhabung von Prioritätswarteschlangen etwas genauer zu betrachten, da wir verschiedene Operationen auf Prioritätswarteschlangen ausführen müssen, um sie zu verwalten und effizient für Anwendungen der obengenannten Art zu benutzen. Tatsächlich besteht der Hauptgrund der Nützlichkeit von Prioritätswarteschlangen, in ihrer Flexibilität, da sie die Möglichkeit geben, eine Vielzahl verschiedenartiger Operationen mit Mengen von Datensätzen mit Schlüsseln effizient auszuführen. Wir möchten eine Datenstruktur aufbauen und unterhalten, die Datensätze mit numerischen Schlüsseln (Prioritäten) enthält und die einige der folgenden Operationen unterstützt:

  1. Aufbauen (construct) einer Prioritätswarteschlange aus N gegebenen Elementen.
  2. Einfügen (insert) eines neuen Elements.
  3. Entfernen (remove) des größten Elements.
  4. Ersetzen (replace) des größten Elements durch ein neues Element (außer wenn das neue Element größer ist).
  5. Verändern (change) der Priorität eines Elements.
  6. Löschen (delete) eines beliebigen angegebenen Elements.
  7. Zusammenfügen (join) von zwei Prioritätswarteschlangen zu einer neuen, größeren.

(Falls Datensätze gleiche Schlüssel haben können, verwenden wir den Begriff »größtes« Element in der Bedeutung »jeder beliebige Datensatz mit dem größten Wert eines Schlüssels«.)

Die Operation replace entspricht fast einem insert, gefolgt von remove (wobei der Unterschied darin besteht, daß insert/remove es erforderlich macht, daß die Prioritätswarteschlange sich vorübergehend um ein Element verlängert); es ist anzumerken, daß dies etwas anderes ist als ein remove, dem ein insert folgt. Dies (replace) ist als eine separate Möglichkeit aufgeführt worden, da einige Implementationen von Prioritätswarteschlangen die Operation replace sehr effizient ausführen können, wie wir sehen werden. In ähnlicher Weise könnte die Operation change als ein delete implementiert werden, dem insert folgt, und construct könnte mit wiederholter Benutzung der Operation insert implementiert werden. Diese Operationen können jedoch für einige Arten von Datenstrukturen auf direktem Wege effizienter implementiert werden. Die Operation join erfordert für eine effiziente Implementation höherentwickelte Datenstrukturen; wir konzentrieren uns jedoch auf eine klassische Datenstruktur, die Heap genannt wird und effiziente Implementationen der ersten fünf Operationen ermöglicht.

Die Prioritätswarteschlange in der oben beschriebenen Form ist ein ausgezeichnetes Beispiel einer abstrakten Datenstruktur, wie sie in Kapitel 3 beschrieben wurde: Sie ist mittels der Operationen, die auf ihr ausgeführt werden, eindeutig definiert, unabhängig davon, wie die Daten in irgendeiner speziellen Implementation organisiert und verarbeitet werden.

Unterschiedliche Implementationen von Prioritätswarteschlangen führen zu unterschiedlichen Kenngrößen der Leistungsfähigkeit für die verschiedenen auszuführenden Operationen, was Abweichungen bei den Kosten zur Folge hat. Tatsächlich sind Unterschiede hinsichtlich der Leistungsfähigkeit die einzigen, die im Zusammenhang mit einer abstrakten Datenstruktur auftreten können. Zuerst wollen wir diesen Punkt illustrieren, indem wir einige elementare Datenstrukturen für die Implementation von Prioritätswarteschlangen betrachten. Anschließend untersuchen wir eine höherentwickelte Datenstruktur und zeigen dann, wie die verschiedenen Operationen unter Verwendung dieser Datenstruktur effizient implementiert werden können. Danach betrachten wir einen wichtigen Sortieralgorithmus, der sich in natürlicher Weise aus diesen Implementationen ergibt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]