Informatiker Board | Algorithmen

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Beweis Max - Heap

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Beweis Max - Heap

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

cirixx
Grünschnabel

Dabei seit: 13.06.2012
Beiträge: 1

Beweis Max - Heap

Zitatantwort auf diesen Beitrag erstellen

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

13.06.2012 16:15

Nehmen Sie cirixx in Ihre Freundesliste auf

HueHang
unregistriert

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.

16.06.2012 13:48

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Beweis Max - Heap