+1 Daumen
1,1k 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.

Avatar 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!

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community