Array-Darstellung des binären Heaps

Ein vollständiger Binärbaum, der der Heap-Sortierungseigenschaft folgt, wird als Binär-Heap bezeichnet.

Basierend darauf, wie ein binärer Heap sortiert ist, kann er in zwei Typen unterteilt werden:

Minimaler Heap ist ein Heap, bei dem der Wert eines Knotens größer oder gleich dem Wert seines übergeordneten Knotens ist. Der Wurzelknoten eines Min-Heaps ist der kleinste.

Max Heap ist ein Heap, bei dem der Wert eines Knotens kleiner oder gleich dem Wert seines übergeordneten Knotens ist. Der Wurzelknoten des Max-Heaps ist der größte.

Der Wert eines binären Heaps wird normalerweise als Array dargestellt. Die Array-Darstellung eines binären Heaps lautet wie folgt:

• Der Index des Wurzelelements ist 0.

• Wenn i der Index eines Knotens im Array ist, lauten die Indizes anderer Knoten, die sich auf diesen Knoten beziehen, wie folgt:

  • Linkes Kind: (2*i)+1

  • Rechtes Kind : (2*i )+2

  • Übergeordneter Knoten: (i-1)/2

Mit den oben genannten Array-Darstellungsregeln können wir den Heap als Array darstellen:

Minimum Heap Array-Darstellung:

1...

– Die Wurzel Knoten hat den Mindestwert. Der Wert des Knotens ist größer als der Wert des übergeordneten Knotens.

Beispiel:

• 1

  4

  7

6

9

. 10

8

Max Heap Array-Darstellung:

– Der Wurzelknoten hat den Maximalwert. Der Wert des Knotens ist kleiner als der Wert des übergeordneten Knotens.

Beispiel:

• 11

  8

  9

6

4

5

1

Das obige ist der detaillierte Inhalt vonArray-Darstellung des binären Heaps. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!