Informatiker Board | Druckvorschau: Beweis Max - Heap

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Beweis Max - Heap (http://www.informatikerboard.de/board/thread.php?threadid=1230)

Geschrieben von cirixx am 13.06.2012 um 16:15:

Beweis Max - Heap

Meine Frage:
Hallo,
haben jetzt in der Vorlesung ein Heapsort (mit MaxHeap Eigenschaft) programmiert. Jetzt sollen wir zeigen, dass für jeden Pfad $[latex](k_{1},k_{2})(k_{2},k_{3})(k_{3},k_{4})..(k_{i-1},k_{i})[/latex]$ für ein Max Heap x das hier gilt: $[latex] x[k_{1}] \geq x[k_{2}] \geq ... \geq x[k_{i}] [/latex]$

Muss man das mit Induktion machen oder gibt es eine andere Methode, brauche irgendwie einen Ansatz

Meine Ideen:
Muss man das mit Induktion machen oder gibt es eine andere Methode, brauche irgendwie einen Ansatz

Geschrieben von HueHang am 16.06.2012 um 13:48:

Also mit Induktion geht's wahrscheinlich am leichtesten. Der Induktionsanfang ist ein Baum mit nur einem Knoten - also der Wurzel.
Die Behauptung ist, dass jedes Kind höchstens so groß ist wie sein Elternknoten. Die Induktion kannst du dann mit den Teilbäumen vollbringen. Ich hoffe, dass diese Ansätze dir weiterhelfen.