====== Min-Heap ======

Ein Min-Heap ist ein spezieller [[struct:heap:start|Heap]] bei dem rekursiv für jeden Knoten ''node'' folgende Heap-Bedingung gilt: Der Wert des Schlüssels des Vaters ist stets kleiner als der Wert des eigenen Schlüssels. Analog existieren Max-Heaps, bei denen analog der Wert des Vaters größer ist als der eigene Wert. Formal kann man für Min-Heaps die Bedingung

''node.parent.key < node.key''

formulieren. Man stelle sich dabei folgende Datenstruktur (im Pseudocode) vor:
<code>Struktur Knoten:
    Knoten parent
    Wert key
</code>
''Wert'' kann dabei ein ''Integer'', ''String'' oder anderer Datentyp sein. Häufig werden ''Integer''-Werte verwendet, für die entsprechend die totale Ordnung (mittels '<') eindeutig definiert ist. Zusätzlich enthält ein solcher Knoten noch die eigentlichen Daten, die hinsichtlich des Schlüssels geordnet werden.

===== Aufbau =====

Prinzipiell ist die Implementierung eines Min-Heaps als Binärbaum möglich. In der Praxis wird allerdings häufig ein Array verwendet [1]. Dafür notwendig ist es, dass die Elemente einer gewissen Struktur innerhalb des Arrays unterliegen, so dass sich zu jedem Knoten (bzw. dessen Index) der Index des Vaterknotens ermitteln lässt.

**Darstellung als Baum:** ([2])
{{ http://upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Min-heap-1.svg/640px-Min-heap-1.svg.png?640 |}}
**Darstellung als Array:**
^-4^2^-3^5^3^8^2^6^9^7^17^17^11^17^20^

Bei genauerer Betrachtung erkennt man, dass ein Heap ein fast vollständiger Baum ist und für ''n'' Elemente stets Höhe ''ld n'' besitzt.

Der Einfachheit halber verwenden wir hier eine Implementierung auf Basis von Binärbäumen. Ein Knoten habe folgende Struktur:
<code>Struktur Knoten
    Knoten parent // Zeiger auf Vater (ggf. NULL)
    Knoten left   // Zeiger auf linkes Kind (ggf. NULL)
    Knoten right  // Zeiger auf rechtes Kind (ggf. NULL)
    Wert key      // Schlüssel-Wert
    Daten value   // eigentliche Daten (nur der Vollständigkeit halber)
</code>

===== Einsatzgebiete =====

Heaps können zur Implementierung der Datenstruktur [[struct:queue:start#priority_queue|Prioritäten-Warteschlange]] verwendet werden. Ein anderes Einsatzgebiet ist der Sortieralgorithmus [[algo:heapsort|Heap-Sort]].

===== Operationen =====

Auf einem Min-Heap werden üblicherweise folgende Operationen ausgeführt:
  * ''minHeapify(heap, node)'' - stellt im ''heap'' ab ''node'' die Heap-Bedingung wieder her, in dem ''node'' nach unten "sickert"
  * ''insert(heap, node)'' - fügt ''node'' in den ''heap'' ein
  * ''decreaseKey(heap, node, key)'' - verringert den Schlüssel von ''node'' im ''heap'' auf den neuen ''keyt''
  * ''extractMin(heap): node'' - liefert den ''node'' des ''heap'' mit dem kleinsten Schlüssel
  * ''delete(heap, node)'' - entfernt ''node'' aus dem ''heap''

Suchen ist auf Heaps generell ineffizient, da keine Struktur existiert, die die Suche unterstützt. Dies ist beispielsweise bei [[struct:tree:bst|binären Suchbäumen]] gegeben.

Zusätzlich existiert in der Praxis eine Funktion zur Erstellung eines Min-Heaps aus einem Array. Darauf wird hier aus Gründen der Einfachheit nicht näher eingegangen.

==== Heap-Bedingung (wieder-)herstellen ====

Wir betrachten folgende Situation: Der Min-Heap ''heap'' ist gegeben. Für ''node'' wollen wir die Heap-Bedingung herstellen. Dabei wird, solange die Heap-Bedingung verletzt ist, ''node'' mit seinem kleinsten Kind getauscht. Es ergibt sich folgender Algorithmus:

<code>function minHeapify(heap, node):
    solange Heap-Bedingung für node verletzt:
        Suche Knoten min mit kleinstem Schlüssel in Kindern von node
        Tausche node mit min
        node := min
</code>

**Laufzeit:** O(ld n), da höchstens ld(n)-viele rekursive Aufrufe (für die Wurzel).

==== Knoten einfügen ====

Um einen Knoten einzufügen wird dieser an das Ende des Baumes gehangen und für ihn die Heap-Bedingung hergestellt. Dies geschieht entsprechend rekursiv bis zur Wurzel.

<code>function insert(heap, node):
    Füge node am Ende von heap ein
    solange node ist nicht Wurzel und Heap-Bedingung für node.parent verletzt:
        Tausche node mit node.parent
        node := node.parent
</code>

**Laufzeit:** O(ld n)

==== Schlüssel verringern ====

Durch das Verringern des Schlüssels eines Knotens, kann die Heap-Bedingung verletzt werden, da der neue Schlüssel ggf. der kleinste eines Teilheaps sein kann. Daher muss ''node'' solange hochgetauscht sein, bis die Heap-Bedingung wieder erfüllt ist

<code>function decreaseKey(heap, node, key):
    node.key = key
    solange node ist nicht Wurzel und Heap-Bedingung für node.parent verletzt:
        Tausche node mit node.parent
        node := node.parent
</code>

**Laufzeit:** O(ld n)

==== Minimum entfernen ====

Möchte man das Minimum eines Min-Heaps entfernen, kann dieses durch das letzte Element des Heaps ersetzt werden. Auf die nun möglicherweise falsch stehende Wurzel muss nun noch ''minHeapify'' angewendet werden. Dies ist gültig, da das zweitkleinste Element des Heaps automatisch eines der Kinder der Wurzel sein muss.

<code>function extractMin(heap):
    min = heap.root
    Ersetze Wurzel durch letztes Element
    minHeapify(heap, heap.root)
    return min
</code>

**Laufzeit:** O(ld n), vgl. ''minHeapify''.

==== Knoten löschen ====
 
Der Schlüssel des zu löschenden Knotens wird auf einen minimalen Wert gesetzt, so dass er in die Wurzel getauscht wird. Anschließend kann er mittels ''extractMin'' entfernt werden. In der Theorie wird dafür -∞ verwendet. Technisch ist die Verwendung des kleinsten Schlüsselwertes (z.B. -128 für einen vorzeichenbehafteten 8-Bit Integer) sinnvoll.

<code>function delete(heap, node):
    decreaseKey(heap, node, -∞)
    extractMin(heap)
</code>

**Laufzeit:** O(ld n), vgl. Teiloperationen.

====== Verweise ======

[1] siehe ''make_heap'' auf [[http://en.cppreference.com/w/cpp/algorithm/make_heap|cppreference.com]]
[2] Quelle Grafik: http://de.wikipedia.org/wiki/Heap_(Datenstruktur)