Aufbau MinHeap < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | MinHeapsort Aufbau.. |
Array größe: 10
Zahlen im Array: 69,33,95,5,18,1,21,16,81,46
69
33 95
5 18 1 21
16 81 46
Das der Baum im Level-order aufgebaut wird, ist mir klar..
Im ersten durchlauf wird 46 mit 18 verglichen. Keine Änderung. Im zweiten durchlauf wird 16 mit 5 verglichen. Auch keine Änderung. Im dritten durchlauf wird 1 mit 95 verglichen. Die 1 nimmt den platz von 95 ein und 95 wandert runter zur eins.. Soweit ist ja noch alles klar.. Das gleiche passiert mit 5 und 33. Hier der neue AVL Baum.
69
5 1
33 18 95 21
16 81 46
Nur was ich nicht ganz so verstehe ist warum wird nun 16 mit 33 verglichen und die 16 nimmt den Platz von der 33 ein und die 33 wandert runter zur 16?? Ich hätte anstatt der 16 und 33 eigentlich in diesem Fall die 1 mit der 69 getauscht, was aber falsch ist.. Kann mir vielleicht einer erklären wie das mit dem Min Heap geht?? Ich steig das an gewissen stellen nicht mehr durch warum die vergleiche irgendwann dann wieder runter gehen und wann das passiert.. :(
# Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:12 Do 23.07.2009 | | Autor: | CSSX |
Du musst dir den Heap als Liste bzw. als Array ansehen. Dabei ist die Wurzel das erste Element, und dann gehst du einfach von links nach rechts in jeder Stufe des Baumes und bildest dir eine Liste. Diese Liste wird jetzt von hinten nach vorne bearbeitet: Für jeden Knoten überprüfst du, ob die Heap-Invariante erfüllt ist.
Wenn du von hinten anfängst, erfüllen die ersten (untersten) Knoten ja bereits die Invariante für den Heap (stelle sie dir als Teilbaum vor): Sie haben keine Kinder die grösser/kleiner sind als sie selbst. Dann gehst du einfach zum nächsten Knoten, bis du zum ersten Knoten kommst welcher kein Blatt ist: Dort tauscht du dann entsprechend den Knoten mit einem der Kinder falls nötig. Diesen Knoten musst du dann aber auch sozusagen weiterverfolgen und "runtersickern" lassen bis keines der Kinder mehr grösser/kleiner ist oder ein Blatt daraus geworden ist.
Du machst bei dem Baum also folgendes:
Prüfe 46 -> OK
Prüfe 81 -> OK
Prüfe 16 -> OK
Prüfe 21 -> OK
Prüfe 1 -> OK
Prüfe 18 -> Tausche mit 46 -> OK
Prüfe 5 -> OK
Prüfe 95 -> Tausche mit 1 -> OK
Prüfe 33 -> Tausche mit 5 -> Tausche mit 16 -> OK
...
und so weiter.
Am Ende sollte dann ein Min-Heap entstehen, d.h. für jeden Knoten sollte die Invariante gelden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:33 Do 23.07.2009 | | Autor: | CSSX |
Sorry, da hat sich ein kleiner Fehler eingeschlichen: Die 18 tauscht man natürlich nicht mit der 46. Ich hoffe es ist trotzdem klar 
|
|
|
|
