Ein Min-Heap ist ein spezieller 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:

Struktur Knoten:
    Knoten parent
    Wert key

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.

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]) Darstellung als Array:

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:

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)

Heaps können zur Implementierung der Datenstruktur Prioritäten-Warteschlange verwendet werden. Ein anderes Einsatzgebiet ist der Sortieralgorithmus Heap-Sort.

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

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:

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

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

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.

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

Laufzeit: O(ld n)

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

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

Laufzeit: O(ld n)

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.

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

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

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.

function delete(heap, node):
    decreaseKey(heap, node, -∞)
    extractMin(heap)

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

[1] siehe make_heap auf cppreference.com [2] Quelle Grafik: http://de.wikipedia.org/wiki/Heap_(Datenstruktur)