Notizen

Heap

tagsdatenstrukturen

Ein Heap, oder auch Binärer Suchbaum ist ein linksvoller Binärbaum. In einem Heap können in logarithmischer Zeit Elemente eingefügt, oder das größte Element (Max-Heap) bzw. das kleinste Element (Min-Heap) entfernt werden.

Beispiele

Min-Heap

Min-Heap-Bedingung: Der Vorgänger eines Knotens ist immer größer als er selbst.

graph TD
    1((1)) --- 2((2))
    1((1)) --- 3((3))
    2((2)) --- 4((4))
    2((2)) --- 5((5))
    3((3)) --- 6((6))
    3((3)) --- 7((7))

Im Min-Heap steht das kleinste Element immer ganz oben.

Funktionen

BuildHeap

  • Startet beim Vorgänger des letzten Knoten
  • Ruft Heapify auf
  • Heapify
  • Usw bis Startknoten

Heapify

Heapify wird aufgerufen, um die Heap-Bedingung aufrecht zu erhalten.

  • Rekursiv wird der Knoten mit den Kindern verglichen
  • MaxHeap: Falls es größere Kinder gibt, tausche mit dem größten
  • Rufe Heapify auf dem getauschten Kind auf

ExtractMin bzw. ExtractMax

Entfernt das erste Element aus dem Heap, zieht das letzte Element an den Anfang und führt Heapify aus.

DecreaseKey

Verändert den Schlüsselwert eines Elements im Heap und führt Heapify aus. Bei einem Min-Heap wird Heapify nach oben ausgeführt, bei einem Max-Heap nach unten.

Backlinks