Robert Sedgewick: Algorithmen

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


11. Prioritätswarteschlangen



Weiterentwickelte Implementationen

Wenn die join-Operation effizient ausgeführt werden muß, sind die bisher angegebenen Implementationen unzureichend und es werden weiterentwickelte Techniken benötigt. Obwohl wir hier nicht die Möglichkeit haben, auf Einzelheiten solcher Methoden einzugehen, können wir einige der Überlegungen erörtern, die bei ihrer Entwicklung anzustellen sind.

Unter »effizient« verstehen wir, daß join ungefähr in der gleichen Zeit ausgeführt werden sollte wie die anderen Operationen. Damit scheidet die von uns verwendete verbindungslose Darstellung für Heaps sofort aus, da zwei große Heaps nur zusammengefügt werden können, indem alle Elemente mindestens eines Heaps in ein großes Feld bewegt werden. Es ist einfach, die von uns betrachteten Algorithmen so zu übertragen, daß verbundene Darstellungen verwendet werden; tatsächlich gibt es manchmal noch andere Gründe, dies zu tun (zum Beispiel könnte es unzweckmäßig sein, ein großes zusammenhängendes Feld zu haben). Bei einer direkten Darstellung mit Verkettungen müßten in jedem Knoten Verkettungen vorgesehen werden, die auf den Vorgänger und beide Nachfolger zeigen.

Es erweist sich, daß die Heap-Bedingung selbst zu stark zu sein scheint, als daß eine effiziente Implementation der join-Operation möglich wäre. Alle höherentwickelten Datenstrukturen, die zur Lösung dieses Problems bestimmt sind, schwächen entweder die Heap-Bedingung oder die Ausgewogenheits-Bedingung ab, um die für join benötigte Flexibilität zu erhalten. Diese Strukturen gestatten die Ausführung aller Operationen in logarithmischer Zeit.


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