Robert Sedgewick: Algorithmen

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


11. Prioritätswarteschlangen



Die Datenstruktur des Heaps

Die Datenstruktur, die wir verwenden werden, um die Operationen mit Prioritätswarteschlangen zu ermöglichen, beinhaltet das Speichern der Datensätze in einem Feld so, daß jeder Schlüssel garantiert größer ist als die Schlüssel auf zwei bestimmten anderen Positionen. Jeder dieser Schlüssel muß wiederum größer sein als zwei weitere Schlüssel usw. Diese Ordnung läßt sich sehr leicht veranschaulichen, indem wir das Feld in Form einer zweidimensionalen Baumstruktur zeichnen, wobei von jedem Knoten Linien nach unten zu den beiden Knoten führen, von denen bekannt ist, daß sie kleiner sind, wie es Abbildung 11.1 zeigt.

Abbildung 11.1
Abbildung 11.1 Darstellung eines Heaps als vollständiger Baum.

Wir erinnern uns (siehe Kapitel 4), daß diese Struktur »vollständiger binärer Baum« genannt wird: Sie kann erzeugt werden, indem ein Knoten (Wurzel genannt) gezeichnet wird und dann nach unten und von links nach rechts fortgefahren wird, indem jeweils zwei Knoten unter einem Knoten der vorangehenden Ebene gezeichnet und mit ihm verbunden werden, bis N Knoten gezeichnet worden sind. Die beiden Knoten unter jedem Knoten werden dessen (direkte) Nachfolger (children) genannt, der Knoten über jedem Knoten heißt dessen (direkter) Vorgänger (parent). Nunmehr fordern wir, daß die Schlüssel im Baum der Heap-Bedingung genügen: Der Schlüssel in jedem Knoten soll größer sein (oder gleich) als die Schlüssel in seinen Nachfolgern (falls er Nachfolger besitzt). Wir bemerken, daß hieraus insbesondere folgt, daß sich der größte Schlüssel in der Wurzel befindet.

Wir können vollständige binäre Bäume sequentiell innerhalb eines Feldes darstellen, indem wir einfach die Wurzel auf die Position 1 setzen, ihre Nachfolger auf die Positionen 2 und 3, die Knoten der folgenden Ebene auf die Positionen 4, 5, 6 und 7 usw., wie die Numerierung in Abbildung 11.1 zeigt. Als Beispiel zeigt Abbildung 11.2 die Darstellung des obigen Baumes als Feld.

Abbildung 11.2
Abbildung 11.2 Darstellung eines Heaps als Feld.

Diese natürliche Darstellungsweise ist nützlich, da es sehr leicht ist, von einem Knoten zu seinem Vorgänger und zu seinen Nachfolgern zu gelangen. Der Vorgänger des Knotens auf Position j befindet sich auf Position j div 2, und die beiden Nachfolger des Knotens auf Position j befinden sich auf den Positionen 2j und 2j + 1. Dadurch wird die Traversierung eines solchen Baumes sogar noch einfacher, als wenn der Baum mit Hilfe einer standardmäßigen Darstellung mit Verkettungen (bei der jedes Element einen Zeiger zu seinem Vorgänger und zu seinen Nachfolgern enthält) implementiert wäre. Die starre Struktur vollständiger binärer Bäume, die als Felder dargestellt sind, schränkt ihren Nutzen als Datenstrukturen ein. Es ist jedoch gerade noch genug Flexibilität vorhanden, um die Implementation von effizienten Algorithmen für Prioritätswarteschlangen zu ermöglichen. Ein Heap ist ein als ein Feld dargestellter vollständiger binärer Baum, in dem jeder Knoten der Heap-Bedingung genügt. Insbesondere befindet sich der größte Schlüssel stets auf der ersten Position im Feld.

Alle Algorithmen operieren entlang eines Pfades (path) von der Wurzel zum unteren Ende des Heaps (indem sie sich einfach vom Vorgänger zum Nachfolger oder vom Nachfolger zum Vorgänger bewegen). Es ist leicht einzusehen, daß sich in einem Heap mit N Knoten auf allen Pfaden etwa lg N Knoten befinden. (Es gibt etwa N/2 Knoten auf der untersten Ebene, N/4 Knoten mit direkten Nachfolgern auf der untersten Ebene, N/8 Knoten mit »Enkeln« auf der untersten Ebene usw. Jede »Generation« besitzt halb so viele Knoten wie die nächste, woraus folgt, daß höchstens lg N Generationen existieren können.) Folglich können alle Operationen mit Prioritätswarteschlangen (mit Ausnahme von join) bei Verwendung von Heaps in logarithmischer Zeit ausgeführt werden.


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