Frage zu Max-Heap

[r.euch]

Hallo.

Ich habe Max-Heap nicht verstanden, also locker bei Wikipedia reingucken, Beispiel abfassen.

Hat aber nicht geholfen, also ab zu fi.de

Insbes. verstehe ich das "Beispiel für die Überführung in einen Max-Heap" nicht.

1.) Warum z.B. wird als allerletzter Schritt nicht A und E getauscht? Das müsste man doch gemäss "Versickern (auch: absinken) heißt, dass man einen Knoten mit dem größeren seiner beiden Nachfolgeknoten vertauscht, falls dieser größer ist als er selbst, und damit so lange fortfährt, bis er keinen Nachfolgeknoten mehr hat, der größer ist als er selbst." tun, oder?

2.) Warum wird das H zweimal versickert? Die Buchstaben sind doch konstant?

Nicht hauen, bitte! oder falls doch, nur ein bisschen

Tschüß

[flashpixx]

Ich habe bei Wiki das hier als Bsp Heap (Datenstruktur) ? Wikipedia

in der das eigentlich sehr einleuchtend bezügl. der mathematischen Ordnung erläutert ist.

Das Bsp in Deiner Schilderung verstehe ich nicht. Gib bitte, wenn dazu Fragen sind, den Link an

Phil

[Klotzkopp]

1.) Warum z.B. wird als allerletzter Schritt nicht A und E getauscht? Das müsste man doch gemäss "Versickern (auch: absinken) heißt, dass man einen Knoten mit dem größeren seiner beiden Nachfolgeknoten vertauscht, falls dieser größer ist als er selbst, und damit so lange fortfährt, bis er keinen Nachfolgeknoten mehr hat, der größer ist als er selbst." tun, oder?

Richtig. Aber im Verlauf der ersten Heap-Erstellung sind A und E niemals in einer Nachfolger-Beziehung. Warum sollten sie also vertauscht werden?

2.) Warum wird das H zweimal versickert? Die Buchstaben sind doch konstant?

Die Heap-Erstellung ist nur ein Teilschritt, der mehrfach durchgeführt werden muss, um das Array zu sortieren. Wenn der Heap erstellt wurde, steht das größte Element ganz vorn. Dann wird durch Vertauschen ein Element aus der untersten Ebene des Heaps an die Wurzel geholt und muss neu versickert werden. Und das kann durchaus mehrfach dasselbe sein.

[r.euch]

Hi

Erstmal dange )

Ich verstehe das animierte Bild unter Heapsort ? Wikipedia nicht, besonders als die Phase als ungefähr ein drittel fertig sortiert ist.

Warum sind die Vergleichspfeile(?) so verteilt?

Ciao

[flashpixx]

Vielleicht etwas abstrakter formuliert:

Du hast einen Heap (Halde), auf die kannst Du Elemente drauf werfe. Jedes Element bekommt einen Schlüssel (Hash) der es auf dem gesamten Heap eindeutig identifiziert.

Nun hast Du aber das Problem, dass wenn Du ein Element suchst, Du im schlimmsten Fall einfach mal alle Schlüssel prüfen musst, bis Du das Element findest => wenn Du die Schlüssel irgendwie vorsortieren kannst, wäre das besser, weil Du in einer sortierten Menge schneller etwas suchen kannst

=> Heapsort

Du nimmst nun den Heap und durchläuft alle Elemente und gibst ihnen einen Schlüssel, den Du nach seiner Größe ordnen kannst. Nun sortierst Du diese Schlüssel in einen Binärbaum ein (ein Knoten eines Binärbaums hat immer genau 2 Nachfolger, in unserem Fall hast Du im Knoten (Vater) den Schlüssel Y stehen, im linken Nachfolger X und im rechten Nachfolger Z _und_ es gilt X < Y < Z). Wenn Du nun den Wurzelknoten betrachtest, dann sind alle Element die im linken Teilbaum hängen kleiner als die Wurzel und alle rechts größer (schau Dir aber dazu einmal einen Binärbaum an).

Wie so ein Baum aussieht hier Binärer Heap ? Wikipedia

Wenn Du aber nun Deinen Heap in diesen Baum überführen willst, weißt Du ja noch nicht, wie der Baum aussieht, d.h. Du weißt nicht wo das Element genau hin muss. Also macht man folgendes, man fügt es einfach ein und erzeugt den Baum neu, in dem man eben dieses Element, das falsch ist (sprich unserer Bedingung X < Y < Z nicht genügt) so lange die Äste hoch wandert, bis es eben an der korrekten Stelle ist.

Wenn Du nun das ganze als sortierte Liste haben willst, dann musst Du diesen Baum nur noch traversieren. Je nach Bedingung X > Y > Z bzw X < Y < Z hast Du eben eine Max bzw MinHeap

Phil

[r.euch]

HHmm, danke Flashpixx, aber das Wikipedia-Bild verstehe ich immer noch nicht.

Kann mich bitte mal jemand vom Schlauch heben?

[flashpixx]

Kann mich bitte mal jemand vom Schlauch heben?

Führe den Algorithmus mit ein paar Elemente per Hand durch. Dann siehst Du es. Nimm eine unsortierte Menge an Zahlen z.B. 1, 8, 5, 9, 4, 12, 3, 2

Phil