Heap (Datenstruktur)

Heap (Datenstruktur)

In der Informatik ist ein Heap (wörtlich Haufen oder Halde) 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. 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, beispielsweise bei Vorrangwarteschlangen.

Inhaltsverzeichnis

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.

Abb.1 Beispiel einer Halde in Baumstruktur (Max-Heap)

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 Implementation 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

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

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 bei dem Sortieralgorithmus Heapsort ein Binärer Heap zum Sortieren eingesetzt. Fibonacci-Heaps finden beim Algorithmus von Dijkstra bzw. Prim Anwendung.


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Heap — (englisch „Haufen“) steht für: eine Datenstruktur, siehe Heap (Datenstruktur) einen speziellen Speicherbereich, siehe Dynamischer Speicher Heap ist auch der Name von folgenden Personen Imogen Heap (* 1977), Sängerin, Komponistin, Musikerin und… …   Deutsch Wikipedia

  • Heap-Sort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Heap Sort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Datenstruktur — In der Informatik ist eine Datenstruktur ein mathematisches Objekt zur Speicherung von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre… …   Deutsch Wikipedia

  • Max-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) 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… …   Deutsch Wikipedia

  • Min-Heap — In der Informatik ist ein Heap (wörtlich Haufen oder Halde) 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… …   Deutsch Wikipedia

  • Fibonacci-Heap — In der Informatik ist ein Fibonacci Heap (englisch heap ‚Halde‘) eine Datenstruktur, ähnlich zu einem Binomial Heap, die sich als Vorrangwarteschlange einsetzen lässt. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger… …   Deutsch Wikipedia

  • Binomial-Heap — In der Informatik ist ein Binomial Heap eine Datenstruktur, genauer ein Heap, der sich, ähnlich wie binäre Heaps, als Vorrangwarteschlange einsetzen lässt. Das heißt, dass in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in …   Deutsch Wikipedia

  • Radix Heap — Ein Radix Heap ist eine Datenstruktur zur Realisation der Operationen einer Vorrangwarteschlange. Hiermit kann dann eine Menge von Elementen, denen jeweils ein Schlüssel zugeordnet ist, verwaltet werden. Die Laufzeit der Operationen ist abhängig… …   Deutsch Wikipedia

  • Binärer Heap — Binärer Min Heap In der Informatik ist ein Binärer Heap eine Datenstruktur, genauer ein Heap, der sich als Vorrangwarteschlange einsetzen lässt, das heißt, es können in beliebiger Reihenfolge effizient Elemente mit festgelegter Priorität in den… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”