Binärer Heap

Binärer Min-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 Implementation 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 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ärer-Baum 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 parent(i) den Elterknoten von i zurückgibt.

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

Ein Heap ist also ein partiell geordneter Baum. Zwischen Kinder- und Elter-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 Elementes in den Heap ein
• remove - entfernt ein Element
• extractMin - extrahiert das Element mit dem kleinsten Schlüssel
• decreaseKey - verringert den Schlüsselwert von einem Element

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 eines 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 von dem Knoten 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 von einem Binärbaum in einem Array. Die eingezeichneten Pfeile sind impliziert durch die Funktionen für die Berechnung der Kinder bzw. Elter-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 von einem Binären Baum wieder her, vorausgesetzt dass der linke bzw. der rechte Teilbaum die Heap-Bedingung erfüllen. Dazu tauscht heapify solange rekursiv Kind- mit Elter-Knoten bis die Heap-Eigenschaft nicht mehr verletzt ist. In Pseudocode:

void heapify(Array H, int i)
  assert(isheap(H, left(i)) && isheap(H, right(i))
  int x = i
  if (left(i) < H.size && H.key(left(i)) < H.key(x)))
    x = left(i)
  if (right(i) < H.size && H.key(right(i)) < H.key(x))
    x = right(i)
  if (x == i)
    return
  H.swap(i, x)
  heapify(H, x)

Die Hilfsfunktionen left bzw. right berechnen den Index des linken bzw. rechten Kind-Knoten 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(height(H)) ist. Da die Höhe des Baumes 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 von zusätzlichen 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 x = i
    if (left(i) < H.size && H.key(left(i)) < H.key(x)))
      x = left(i)
    if (right(i) < H.size && H.key(right(i)) < H.key(x))
      x = right(i)
    if (x == i)
      break
    H.swap(i, x)
    i = x
  } while(true)

Wegen dem sukzessiven Tauschen (oder „Schieben“) von einem Knoten in einen Teilbaum herab wird die heapify Operation auch als sift-down („Sieben“) bzw. Sift-Down-Phase bezeichnet.

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 = array.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 von einem Heap-Element 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 Element am Ende um ein neues Element 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)

Remove

Das Entfernen eines Elementes mittels remove geschieht, indem das zu entfernende Element aus seiner Position im Heap entfernt und an seine Stelle das am Ende des Heaps befindliche Element gesetzt wird. Anschließend wird mittels heapify die Heap-Eigenschaft für das verschobene Element wiederhergestellt:

remove(Array h, int i)
  assert(isheap(h))
  assert(i<h.size)
  temp = h[i]
  int l = h.size-1
  h.swap(l, i)
  h.resize(l-1)
  heapify(h, i)
  return temp

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:

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

Get-Min

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

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

Literatur

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

Siehe auch

• Binomial-Heap
• Fibonacci-Heap