Beweis Max - Heap

13.06.2012, 16:15	Auf diesen Beitrag antworten »
cirixx	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


16.06.2012, 13:48	Auf diesen Beitrag antworten »
HueHang	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.

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »