Binärer Heap

Ein Binärer Heap ist eine Datenstruktur aus der Informatik zum effizienten Sortieren von Elementen. Das asymptotisch optimale Sortierverfahren Heapsort verwendet als zentrale Datenstruktur einen binären Heap. Des Weiteren wird der binäre Heap zur Implementierung einer Vorrangwarteschlange, in der das Element mit der höchsten Priorität effizient abgefragt und entfernt werden kann, verwendet. Die Priorität der Elemente wird diesen durch Schlüssel aufgeprägt. Über der Menge der Schlüssel muss daher eine totale Ordnung bestehen, wie sie zum Beispiel die Kleiner-Relation (<) über den ganzen Zahlen darstellt.

In der Literatur wird oft der Zusatz binär weggelassen, so dass je nach Zusammenhang der Heap als archetypische (binäre) Heap-Struktur (implementiert in einem Array) oder die Klasse aller Heap-Datenstrukturen gemeint ist. Des Weiteren wird bei Verwendung der Ordnungsrelation $<$ bzw. $>$ ein Heap als Min-Heap bzw. Max-Heap bezeichnet. Da sich die Operationen im Min- und Max-Heap nur durch die verwendete Ordnungsrelation unterscheiden, wird im Folgenden der binäre Heap und die Operationen darauf am Beispiel des Min-Heap definiert.

Definition Min-Heap

Ein Binärbaum $H$ ist ein Min-Heap, wenn für jeden Knoten $i$ mit $i\neq {\text{root}}$ gilt:

${\text{key}}(H,i)\geq {\text{key}}(H,{\text{parent}}(i))$

Wobei ${\text{parent}}(i)$ den Elternknoten von $i$ bezeichnet.

Diese Eigenschaft wird als (Min-)Heap-Eigenschaft bezeichnet.

Ein Heap ist also ein partiell geordneter Baum. Zwischen Kinder- und Eltern-Knoten besteht eine Ordnung, aber die Kinder-Knoten sind nicht untereinander geordnet.

Operationen

Ein binärer Heap kann effizient mit linearem Zeitaufwand in $O(n)$ konstruiert werden, wobei $n$ die Anzahl der Elemente aus der Eingabe bezeichnet. Folgende Operationen arbeiten auf einem Heap und haben eine Worst-Case-Laufzeit von $O(\log n)$ :

insert – fügt ein neues Element in den Heap ein
remove – entfernt ein Element
extractMin – extrahiert das Element mit dem kleinsten Schlüssel
decreaseKey – verringert den Schlüsselwert eines Elements

Die Operation getMin liefert das kleinste Element im Heap zurück und benötigt dafür konstanten Rechenaufwand.

Struktur

Ein Binärer Heap besteht aus einem Binärbaum, bei dem alle Schichten bis auf die letzte vollständig aufgefüllt sein müssen. Die letzte Schicht des Baumes muss linksbündig aufgefüllt werden. Diese Struktur garantiert, dass der Baum balanciert ist.

Zusätzlich muss der Binärbaum die Heap-Bedingung erfüllen: am Beispiel des Min-Heaps (siehe Abbildung) muss der Schlüssel jedes Kindes eines Knotens größer-gleich dem Schlüssel des Knotens selbst sein. Die Heap-Eigenschaft garantiert, dass sich an der Wurzel immer der Knoten mit dem kleinsten Key befindet.

Häufig wird ein Binärer Heap nicht explizit mit Zeigern konstruiert, sondern durch ein Array abgebildet. Will man einen Binären Heap in einem Array speichern, so wird die Wurzel des Baums an der ersten Position im Array gespeichert. Bei einer Array-Indizierung beginnend mit $1$ werden die beiden Nachfolger des Knotens an der $i$ -ten Position an der $2i$ -ten und $2i+1$ -ten Position gespeichert, entsprechend der Kekule-Nummerierung. Analog dazu sind die Nachfolger des Knotens mit Index $i$ an der $2i+1$ -ten und $2i+2$ -ten Position gespeichert, wenn die Array-Indizierung mit 0 beginnt.

Beispiel für die implizite Darstellung eines Binärbaums in einem Array. Die eingezeichneten Pfeile sind implizit durch die Funktionen für die Berechnung der Kinder bzw. Eltern-Indizes gegeben.

Algorithmen

Bei der Analyse der Algorithmen wird die Heapgröße bzw. die Anzahl der Elemente im Heap-Array mit $n$ bezeichnet.

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 $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 $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 $n/2-1$ nur noch Blätter, also 1-elementige Heaps, gespeichert sind. Das heißt ab $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 $O(n)$ , was nicht direkt offensichtlich ist. Denn heapify ist in $O(\log n)$ und wird $n$ -mal aufgerufen. Die lineare Laufzeit ergibt sich aus folgender Gleichung:

$\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 $h$ über die Baumhöhe iteriert und ${\frac {n}{2^{h+1}}}$ die Anzahl der Teilbäume auf Level $h+1$ bzw. die Anzahl der Kinder aller Knoten der Höhe $h$ berechnet.

Decrease-Key

Wird der Schlüssel eines Heap-Elements $i$ verringert, so muss gegebenenfalls die Heap-Eigenschaft in den Vorgängerknoten wiederhergestellt werden. Die Heap-Eigenschaft in den Kinder-Teilbäumen von $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 $\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 $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: $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: $O(1)$

Siehe auch

Literatur

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 127 (englisch).
Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Volume 3: Sorting and Searching. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 144 (englisch).