Heap (Datenstruktur) - LinkFang.de





Heap (Datenstruktur)


Dieser Artikel behandelt die Datenstruktur Heap; für Heap-Speicher siehe Dynamischer Speicher.

Ein Heap (englisch wörtlich: Haufen oder Halde) in der Informatik ist eine zumeist auf Bäumen basierende abstrakte Datenstruktur. In einem Heap können Objekte oder Elemente abgelegt und aus diesem wieder entnommen werden. Sie dienen damit der Speicherung von Mengen. Den Elementen ist dabei ein Schlüssel zugeordnet, der die Priorität der Elemente festlegt. Häufig werden auch die Elemente selbst als Schlüssel verwendet.

Über die Menge der Schlüssel muss daher eine totale Ordnung festgelegt sein, über welche die Reihenfolge der eingefügten Elemente festgelegt wird. Beispielsweise könnte die Menge der ganzen Zahlen zusammen mit der Kleinerrelation (<) als Schlüsselmenge fungieren.

Der Begriff Heap wird häufig als bedeutungsgleich zu einem partiell geordneten Baum verstanden (vgl. folgendes Bild, das ein Beispiel für einen Min-Heap darstellt). Gelegentlich versteht man einschränkend nur eine besondere Implementierungsform eines partiell geordneten Baums, nämlich die Einbettung in ein Array, als Heap.

Verwendung finden Heaps vor allem dort, wo es darauf ankommt, schnell ein Element mit höchster Priorität aus dem Heap zu entnehmen (HIFO-Prinzip), beispielsweise bei Vorrangwarteschlangen.

Operationen

Je nach Art unterstützen Heaps eine ganze Reihe von Operationen. Die wichtigsten Operationen sind

insert
zum Einfügen eines Elementes,
remove
zum Entfernen eines Elementes und
extractMin
zur Rückgabe und dem Entfernen eines Elementes mit minimalem Schlüssel (=höchster Priorität).

Daneben werden häufig auch die Operationen changeKey zum Anpassen des Schlüssels und merge zum Verschmelzen zweier Heaps bereitgestellt. Die Operation changeKey wird häufig durch die Nacheinanderausführung der Operationen remove und insert gebildet, wobei nach dem Entfernen und vor dem erneuten Einfügen der Schlüssel angepasst wird. In einigen Fällen bieten Heaps statt changeKey lediglich die Operation decreaseKey an, bei der der Schlüssel lediglich verkleinert werden darf.

Heap-Bedingung

Man unterscheidet Heaps in Min-Heaps und Max-Heaps. Bei Min-Heaps bezeichnet man die Eigenschaft, dass die Schlüssel der Kinder eines Knotens stets größer als der Schlüssel ihres Vaters sind, als Heap-Bedingung. Dies bewirkt, dass an der Wurzel des Baumes stets ein Element mit minimalem Schlüssel im Baum zu finden ist. Umgekehrt verlangt die Heap-Bedingung bei Max-Heaps, dass die Schlüssel der Kinder eines Knotens stets kleiner als die ihres Vaters sind. Hier befindet sich an der Wurzel des Baumes immer ein Element mit maximalem Schlüssel.

Mathematisch besteht der Unterschied zwischen beiden Varianten nur in ihrer gegensätzlichen Ordnung der Elemente. Da die Definition von auf- und absteigend rein willkürlich ist, ist es also eine Auslegungsfrage, ob es sich bei einer konkreten Implementierung um einen Min-Heap oder um einen Max-Heap handelt.

Oft kommt es auch vor, dass ein Heap die Heapeigenschaft in beiden Richtungen abbilden soll. In diesem Fall werden einfach zwei Heaps geschaffen, wobei der eine nach der Kleiner- und der andere nach der Größer-Relation anordnet. Eine derartige Datenstruktur wird dann Doppelheap oder kurz Deap genannt.

Bei der Verwendung von Doppel-Heaps ist zu beachten, dass nicht jede Implementierung von Heaps dabei ihr Laufzeitverhalten für die einzelnen Operationen behält. Zum Beispiel unterstützen Fibonacci-Heaps nur ein decreaseKey zum Verringern der Schlüssel mit amortisiert konstanter Laufzeit. Ein allgemeineres changeKey zum Ändern des Schlüssels, welches man im Falle eines derartigen Doppel-Heaps benötigen würde, braucht aber amortisiert mindestens logarithmische Laufzeit.

Eine Variante von Heaps, die die Heap-Bedingung nur eingeschränkt bzw. in abgewandelter Form unterstützt, sind so genannte Min-Max-Heaps. Dabei handelt es sich um Doppel-Heaps, die durch die abgewandelte Form der Heap-Bedingung die Daten in nur einem Baum halten können.

Varianten von Heaps

Es existieren zahlreiche Arten von Heaps mit unterschiedlich gutem Laufzeitverhalten für die verschiedenen Operationen, die sie zur Verfügung stellen. Beispiele für Heaps sind:

Außerdem gibt es mit Soft Heaps eine Variante bei der ein besseres Laufzeitverhalten erreicht wird, indem ein bestimmter Anteil der Schlüssel verdorben werden kann. Diese verdorbenen Schlüssel haben nicht mehr ihren ursprünglichen Wert.

Laufzeitverhalten verschiedener Heap-Arten

Die folgende Tabelle gibt die worst-case Laufzeiten von verschiedenen Heaps bezüglich ihrer Operationen an.

Operation Binärer Heap Binomial Heap Fibonacci Heap Pairing Leftist 2-3 Treap Beap
amortisiert amortisiert amortisiert
extract-min [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math]
remove [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math]
insert [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)[/math] [math]\mathcal{O}(\log n)[/math] ([math]\mathcal{O}(1)[/math] vermutet) [math]\mathcal{O}(1)[/math] oder [math]\mathcal{O}(\log n)[/math]
decrease-key [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)[/math] [math]\mathcal{O}(\log n)[/math] ([math]\mathcal{O}(1)[/math] vermutet) [math]\mathcal{O}(1)[/math] oder [math]\mathcal{O}(\log n)[/math]
merge [math]\mathcal{O}(n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)[/math] [math]\mathcal{O}(\log n)[/math] ([math]\mathcal{O}(1)[/math] vermutet) [math]\mathcal{O}(1)[/math] oder [math]\mathcal{O}(\log n)[/math]

Anwendung

Heaps haben ein breites Spektrum an Anwendungen. Häufig ist vor allem der Einsatz in Vorrangwarteschlangen, wie sie bei Servern oder Betriebssystemen zur Festlegung der Ausführungsreihenfolge von Aufgaben benötigt werden.

Daneben gibt es aber auch Anwendungen, die nicht explizit den Einsatz von Warteschlangen verlangen. Allgemein stellt ein Heap eine ideale Datenstruktur für Greedy-Algorithmen dar, die schrittweise lokale optimierte Entscheidungen treffen. So wird zum Beispiel beim Sortieralgorithmus Heapsort ein Binärer Heap zum Sortieren eingesetzt. Fibonacci-Heaps finden beim Algorithmus von Dijkstra bzw. Prim Anwendung.

Siehe auch

Literatur


Kategorien: Datenstruktur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Heap (Datenstruktur) (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.