Heapify

Die Basis mehrerer Heap-Operationen bildet die Funktion heapify. Sie stellt gegebenenfalls die Heap-Bedingung eines Binärbaums wieder her, vorausgesetzt, dass der linke und der rechte Teilbaum die Heap-Bedingung erfüllen. Dazu tauscht heapify solange rekursiv absteigend Kind- mit Eltern-Knoten, bis die Heap-Eigenschaft nicht mehr verletzt ist.

Anders formuliert, wenn einer der beiden Kindknoten zur aktuell betrachteten Elternebene aufsteigt, sinkt der Elternknoten in der Folge rekursiv so weit herab, bis er die Ebene seines Gewichtes erreicht hat. Wegen des sukzessiven Tauschens (oder „Schiebens“) von einem Knoten in einen Teilbaum herab, wird die heapify Operation auch als sift-down („Sieben“) bzw. Sift-Down-Phase bezeichnet.

In Pseudocode:

void heapify(Array H, int i)
  assert(isheap(H, left(i)) && isheap(H, right(i)))
  int min = i
  if (left(i) < H.size && H.key(left(i)) < H.key(min))
    min = left(i)
  if (right(i) < H.size && H.key(right(i)) < H.key(min))
    min = right(i)
  if (min != i) {
    H.swap(i, min)
    heapify(H, min)
  }

Die Hilfsfunktionen left bzw. right berechnen den Index des linken bzw. rechten Kind-Knotens im Heap-Array, key abstrahiert von dem Zugriff auf dieses Array und swap vertauscht zwei Elemente in dem Array, in dem der Heap gespeichert ist. Die Funktion traversiert den Baum nur in die Tiefe, so dass ihre Laufzeit in ${\displaystyle O({\text{height}}(H))}$ ist. Da die Höhe des Baums logarithmisch von der Anzahl seiner Elemente abhängt, benötigt die Funktion heapify im Worst-Case logarithmische Laufzeit bzgl. der Größe des Heaps, also ${\displaystyle O(\log n)}$. heapify benötigt nur eine konstante Anzahl zusätzlicher Speicherzellen, weil sie tail rekursiv ist. Das heißt, dass die Rekursion manuell oder automatisch durch eine Schleife ohne Stack ersetzt werden kann:

void heapify(Array H, int a)
  int i = a
  do {
    assert(isheap(H, left(i)) && isheap(H, right(i))
    int min = i
    if (left(i) < H.size && H.key(left(i)) < H.key(min))
      min = left(i)
    if (right(i) < H.size && H.key(right(i)) < H.key(min))
      min = right(i)
    if (min == i)
      break
    H.swap(i, min)
    i = min
  } while(true)

Build

Die Funktion build konstruiert einen Heap aus einem Array, indem sie iterativ die Funktion heapify aufruft. Sie beginnt bei den Blättern, die per Definition die Heap-Eigenschaft erfüllen, und arbeitet sich schrittweise zur Wurzel vor. Diese Arbeitsweise wird auch als bottom-up bezeichnet. Als Pseudocode:

void build(Array a)
  if (a.empty)
    return
  for (int i = a.size/2-1; i>=0; --i)
    heapify(a, i)

Aus der Struktur des binären Heap, der in einem Array gespeichert ist, ergibt sich, dass ab Position ${\displaystyle n/2-1}$ nur noch Blätter, also 1-elementige Heaps, gespeichert sind. Das heißt ab ${\displaystyle n/2-1}$ beginnt die unterste Ebene (Level) des binären Baums. Da die Baumelemente im Array in level-order gespeichert sind, läuft die Iteration sukzessive jeweils vom letzten bis ersten Elements eines Levels.

Die Laufzeit von build ist in ${\displaystyle O(n)}$, was nicht direkt offensichtlich ist. Denn heapify ist in ${\displaystyle O(\log n)}$ und wird ${\displaystyle n}$-mal aufgerufen. Die lineare Laufzeit ergibt sich aus folgender Gleichung:

${\displaystyle \sum _{h=0}^{\left\lfloor \log n\right\rfloor }\left\lceil {\frac {n}{2^{h+1}}}\right\rceil O(h)=O\left(n\sum _{h=0}^{\left\lfloor \log n\right\rfloor }{\frac {h}{2^{h}}}\right)=O(n)}$

wobei ${\displaystyle h}$ über die Baumhöhe iteriert und ${\displaystyle {\frac {n}{2^{h+1}}}}$ die Anzahl der Teilbäume auf Level ${\displaystyle h+1}$ bzw. die Anzahl der Kinder aller Knoten der Höhe ${\displaystyle h}$ berechnet.

Decrease-Key

Wird der Schlüssel eines Heap-Elements ${\displaystyle i}$ verringert, so muss gegebenenfalls die Heap-Eigenschaft in den Vorgängerknoten wiederhergestellt werden. Die Heap-Eigenschaft in den Kinder-Teilbäumen von ${\displaystyle i}$ wird durch die decrease-key Operation nicht verändert. decrease-key arbeitet wie build bottom-up:

void decrease(Array H, int i, newkey)
  assert(isheap(H, 0))
  assert(H.key(i) >= newkey)
  H.key(i) = newkey
  while (i > 0 && H.key(i) < H.key(parent(i)))
    H.swap(i, parent(i))
    i = parent(i)

Insert

Das Einfügen eines Elementes mittels insert erfolgt, indem das Heap-Array um ein neues Element am Ende mit dem Wert ${\displaystyle \inf }$ erweitert wird, worauf die Funktion decrease mit dem einzufügenden Schlüssel aufgerufen wird, damit die möglicherweise verletzte Heap-Eigenschaft wieder hergestellt wird:

void insert(Array H, newkey)
  assert(isheap(H))
  int i = H.size
  H.resize(i+1)
  H.key(i) = inf
  decrease(H, i, newkey)

Die Laufzeit ist entsprechend ${\displaystyle O(\log n)}$

Remove

Das Entfernen eines Elementes mittels remove geschieht, indem das zu entfernende Element aus seiner Position i im Heap entfernt und an seine Stelle das sich am Ende des Heaps befindende Element gesetzt wird. Anschließend muss die Heap-Eigenschaft an Position i wiederhergestellt werden. Dabei kann es sowohl vorkommen, dass das Element auf Position i größer ist als sein Elternknoten, als auch dass es kleiner ist. Dementsprechend muss es mittels heapify nach unten oder mittels decrease nach oben verschoben werden.

Der decrease-Fall mag nicht offensichtlich sein. Wieso sollte das vormals letzte Element des Arrays kleiner sein als ein viel weiter oben im Baum gelöschtes Element? Das liegt daran, dass ein Heap nur eine partielle und keine totale Ordnung repräsentiert. Betrachtet man den ersten gemeinsamen Vorfahren von zu löschendem und letztem Element, so kann es sein, dass sich in dem einen Teilbaum mit dem letzten Element nur sehr kleine Elemente befinden, wohingegen der andere Teilbaum mit dem zu löschenden Element größere Elemente enthält. Hier ist ein Beispiel einer solchen Situation. Das Element mit dem Index 5 soll gelöscht werden:

h1 = [0, 1, 2, 2, 1, 2, 2, 2, 2, 1] // ist ein korrekter Heap
-> [0, 1, 2, 2, 1, 1, 2, 2, 2, 2] // nach dem Swap mit dem letzten Element
-> [0, 1, 2, 2, 1, 1, 2, 2, 2] // nach dem Entfernen des nun letzten Elements

Nach dem Entfernen des letzten Elements verletzt das sich jetzt an Index 5 befindende Element 1 zusammen mit seinem Elternknoten 2 die Heap-Eigenschaft. Ein Anwenden von heapify würde das Array nicht ändern, da die Funktion nur Elemente nach unten schiebt. Bei Index 5 handelt es sich aber bereits um einen Blatt-Knoten. Stattdessen müssen wir das Element an Position 5 nach oben schieben. Dies geschieht mit der Funktion decrease.

Element remove(Array H, unsigned int i)
  assert(isheap(H))
  assert(i<H.size)
  removedItem = H[i]
  int lastIdx = H.size-1
  H.swap(i,lastIdx)
  H.resize(lastIdx)
/*  Im Fall i == lastIdx wurde die Heap-Eigenschaft durch das Entfernen
    des Elements beibehalten, und i befindet sich nun ''out of bounds'',
    weil das Array verkleinert wurde. Ein Aufruf von heapify oder
    decrease würde zum Absturz führen. */
  if ( i != lastIdx ) {
    if ( i == 0 || H.key(i) > H.key(parent(i)) ) {
      heapify(H, i)
    } else {
      decrease(H, i, H.key(i)) // decrease macht nichts, wenn H.key(i) == H.key(parent(i))
    }
  }
  return removedItem

Extract-Min

Das Zurückgeben und Entfernen eines Elementes mittels extractMin gestaltet sich ähnlich wie remove. Das minimale Element befindet sich wegen der Heap-Bedingung an der Wurzel des Baumes und stellt damit das zu entfernende Element dar:

Element extractMin(Array H)
  assert(isheap(H))
  assert(H.size > 0)
  return remove(H, 0)

Die Laufzeit ist entsprechend: ${\displaystyle O(\log n)}$

Get-Min

Die getMin gibt das kleinste Element in einem Heap zurück. Aus der Heap-Eigenschaft folgt direkt, dass das kleinste Element immer an der ersten Array-Position, also der Wurzel des binären Baums steht. Im Pseudo-Code:

Element getMin(Array H)
  assert(isheap(H))
  assert(H.size > 0)
  return H.key(0)

Die Laufzeit ist entsprechend konstant: ${\displaystyle O(1)}$