+1 Punkt
53 Aufrufe

Angenommen ein Max-Heap enthält nur verschiedene Elemente. Wo im Array kann sich das kleinste Element befinden (Index)?

Müsste das nicht [2^{h-1}; 2^{h+1}-1] sein?


Nachtrag:

k sollte h sein (nun korrigiert) und beschreibt die Höhe des Heaps. Zum Array wurden keine Angaben gemacht. Ich denke wir sollen nur die Reichweite in der sich das kleinste Elemente befinden könnte zeigen. Also müssten das die Blätter sein, wenn man das Heap als Binärbaum betrachtet.

Gefragt von

1 Antwort

0 Daumen
 
Beste Antwort

Ein Max-Heap hat die Eigenschaft, dass der Wert eines jeden Parent-Knoten größer oder gleich den Werten der Child-Knoten ist. Das kleinste Element befindet sich in irgendeinem der Blätter. In welchem genau, lässt sich ohne weitere Informationen nicht sagen.

Also müssten das die Blätter sein, wenn man das Heap als Binärbaum betrachtet. 

Korrekt!

Beantwortet von 7,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...