Die Heapbedingung

Ein Feld f[1] bis f[N] mit Schlüsseln bildet einen Heap wenn die folgende Bedingung gilt:

Heapbedingung

f[i]<=f[i/2] für 2<= i <= N]
oder
f[i]>=f[2*i] und f[i]>=f[2*i+1] für 2*i<=N und 2*i+1<= N

Die Heapbedingung lässt sich leichter grafisch in einer Baumdarstellung verdeutlichen:

Beispiel Heapkriterium

Das Feld f mit der Feldgröße N=9

  • f[1] = 9
  • f[2] = 8
  • f[3] = 7
  • f[4] = 3
  • f[5] = 6
  • etc.

genügt der Heapbedingung da jeder obere Knoten größer als die beiden Unterknoten ist.

Die Position im Feld wird hier in rot dargestellt. Der Schlüssel (Wert) des Feldelements hat einen gelben Hintergrund