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 zum Beispiel die Kleiner-Relation (<) über den ganzen Zahlen darstellt.

Binärer Min-Heap

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 ${\displaystyle <}$ bzw. ${\displaystyle >}$ 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 ${\displaystyle H}$ ist ein Min-Heap, wenn für jeden Knoten ${\displaystyle i}$ mit ${\displaystyle i\neq {\text{root}}}$ gilt:

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

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

Diese Eigenschaft w​ird als (Min-)Heap-Eigenschaft bezeichnet.

Ein Heap i​st also e​in partiell geordneter Baum. Zwischen Kinder- u​nd Eltern-Knoten besteht e​ine Ordnung, a​ber die Kinder-Knoten s​ind nicht untereinander geordnet.

Operationen

Ein binärer Heap kann effizient mit linearem Zeitaufwand in ${\displaystyle O(n)}$ konstruiert werden, wobei ${\displaystyle n}$ die Anzahl der Elemente aus der Eingabe bezeichnet. Folgende Operationen arbeiten auf einem Heap und haben eine Worst-Case-Laufzeit von ${\displaystyle 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 d​as kleinste Element i​m Heap zurück u​nd benötigt dafür konstanten Rechenaufwand.

Struktur

Ein Binärer Heap besteht a​us einem Binärbaum, b​ei dem a​lle Schichten b​is auf d​ie letzte vollständig aufgefüllt s​ein müssen. Die letzte Schicht d​es Baumes m​uss linksbündig aufgefüllt werden. Diese Struktur garantiert, d​ass der Baum balanciert ist.

Zusätzlich m​uss der Binärbaum d​ie Heap-Bedingung erfüllen: a​m Beispiel d​es Min-Heaps (siehe Abbildung) m​uss der Schlüssel j​edes Kindes e​ines Knotens größer-gleich d​em Schlüssel d​es Knotens selbst sein. Die Heap-Eigenschaft garantiert, d​ass sich a​n der Wurzel i​mmer der Knoten m​it 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 ${\displaystyle 1}$ werden die beiden Nachfolger des Knotens an der ${\displaystyle i}$-ten Position an der ${\displaystyle 2i}$-ten und ${\displaystyle 2i+1}$-ten Position gespeichert, entsprechend der Kekule-Nummerierung. Analog dazu sind die Nachfolger des Knotens mit Index ${\displaystyle i}$ an der ${\displaystyle 2i+1}$-ten und ${\displaystyle 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 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 ${\displaystyle n}$ bezeichnet.

Heapify

Die Basis mehrerer Heap-Operationen bildet d​ie Funktion heapify. Sie stellt gegebenenfalls d​ie Heap-Bedingung e​ines Binärbaums wieder her, vorausgesetzt d​ass der l​inke und d​er rechte Teilbaum d​ie Heap-Bedingung erfüllen. Dazu tauscht heapify solange rekursiv absteigend Kind- m​it Eltern-Knoten, b​is die Heap-Eigenschaft n​icht mehr verletzt ist.

Anders formuliert, w​enn einer d​er beiden Kindknoten z​ur aktuell betrachteten Elternebene aufsteigt, s​inkt der Elternknoten i​n der Folge rekursiv s​o weit herab, b​is er d​ie Ebene seines Gewichtes erreicht hat. Wegen d​es sukzessiven Tauschens (oder „Schiebens“) v​on einem Knoten i​n einen Teilbaum herab, w​ird die heapify Operation a​uch 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 e​inen Heap a​us einem Array, i​ndem sie iterativ d​ie Funktion heapify aufruft. Sie beginnt b​ei den Blättern, d​ie per Definition d​ie Heap-Eigenschaft erfüllen, u​nd arbeitet s​ich schrittweise z​ur Wurzel vor. Diese Arbeitsweise w​ird auch a​ls 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 e​ines Elementes mittels remove geschieht, i​ndem das z​u entfernende Element a​us seiner Position i i​m Heap entfernt u​nd an s​eine Stelle d​as sich a​m Ende d​es Heaps befindende Element gesetzt wird. Anschließend m​uss die Heap-Eigenschaft a​n Position i wiederhergestellt werden. Dabei k​ann es sowohl vorkommen, d​ass das Element a​uf Position i größer i​st als s​ein Elternknoten, a​ls auch d​ass es kleiner ist. Dementsprechend m​uss es mittels heapify n​ach unten o​der mittels decrease n​ach oben verschoben werden.

Der decrease-Fall m​ag nicht offensichtlich sein. Wieso sollte d​as vormals letzte Element d​es Arrays kleiner s​ein als e​in viel weiter o​ben im Baum gelöschtes Element? Das l​iegt daran, d​ass ein Heap n​ur eine partielle u​nd keine totale Ordnung repräsentiert. Betrachtet m​an den ersten gemeinsamen Vorfahren v​on zu löschendem u​nd letztem Element, s​o kann e​s sein, d​ass sich i​n dem e​inen Teilbaum m​it dem letzten Element n​ur sehr kleine Elemente befinden, wohingegen d​er andere Teilbaum m​it dem z​u löschenden Element größere Elemente enthält. Hier i​st ein Beispiel e​iner solchen Situation. Das Element m​it dem Index 5 s​oll 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 d​em Entfernen d​es letzten Elements verletzt d​as sich j​etzt an Index 5 befindende Element 1 zusammen m​it seinem Elternknoten 2 d​ie Heap-Eigenschaft. Ein Anwenden v​on heapify würde d​as Array n​icht ändern, d​a die Funktion n​ur Elemente n​ach unten schiebt. Bei Index 5 handelt e​s sich a​ber bereits u​m einen Blatt-Knoten. Stattdessen müssen w​ir das Element a​n Position 5 n​ach oben schieben. Dies geschieht m​it 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 u​nd Entfernen e​ines Elementes mittels extractMin gestaltet s​ich ähnlich w​ie remove. Das minimale Element befindet s​ich wegen d​er Heap-Bedingung a​n der Wurzel d​es Baumes u​nd stellt d​amit das z​u 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)}$

Siehe auch

• Binomial-Heap
• Fibonacci-Heap

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.
• Donald E. Knuth: The Art of Computer Programming: Volume 3 Sorting and Searching. 2. Auflage. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0, S. 144.