Doppelheap

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.

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 konstanter amortisierter 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:

• Binärer Heap
  • Min-Max-Heap
• Binomial-Heap
• Fibonacci-Heap
• Treap
• Radix-Heap

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.