Diskussion:Bottom-Up-Heapsort

Versenkungspfad

Zunächst wird der Pfad, in welchem das Wurzelelement versenkt werden soll, bestimmt.

Aber wie wird dieser Pfad bestimmt? -- Paul E. 20:37, 25. Sep 2005 (CEST)

Ich hab das mal hinzugefügt, ist zwar nicht schwierig den Pfad zu bestimmen, aber nicht unbedingt sofort ersichtlich. (14.2.2006 10:45)

Stabilität

Kann jemand noch ergänzen ob der Algorithmus stabil ist? [ist von Benutzer:85.178.138.60, 2006-07-03 --84.150.161.185 18:59, 10. Jul 2006 (CEST)]

Nachdem der Algorithmus im Endeffekt in jedem Schritt exakt das tut, was auch normales Heapsort tut (was durch die eingesparten Vergleiche zu weit abgesenkt wird, wird sofort wieder rückgängig gemacht), ist er ebenso wenig stabil. --84.150.161.185 18:59, 10. Jul 2006 (CEST)

"u. a. 1990"

Die Formulierung im Einleitungssatz überzeugt nicht recht, den wörtlich genommen hiesse es, dass Ingo Wegener das Ding nicht nur 1990, sondern auch noch in anderen Jahren "vorgestellt" habe, was wenig Sinn ergibt. Gemeint ist wohl, dass Ingo Wegener nicht der eindeutige Erfinder ist, da sich auch andere z. T. früher Ähnliches entdeckten. Müsste sich aber ein Informatiker dazu äussern, der weiss, was wirklich gemeint ist.--Xeno06 18:04, 5. Dez. 2007 (CET)

Mehr Vertauschungen = Vorteil?

Alternativ kann man auch die Verschiebung von vornherein auf Verdacht bis zur Blattebene durchführen und später – soweit notwendig – wieder rückgängig machen. Wo Kopien relativ günstig durchgeführt werden können (weil etwa nur ein Zeiger kopiert wird), kann das insgesamt vorteilhaft sein.

Das verstehe ich nicht. Spart man sich dadurch Vergleiche ein? Wenn ja, welche? Falls nicht, wo genau ist dann der Vorteil? Signatur vergessen: 77.188.50.52 01:29, 17. Mär. 2008 (CET)

Auch wenn es jetzt etwas spät ist: Ja, man spart einen Vergleich ein für jede Ebene, über die das Element abgesenkt wird. Denn es muss nicht geprüft werden, ob das abzusenkende Element überhaupt noch weiter abgesenkt werden muss (was einen Vergleich erfordert), sondern man tut es einfach. Man spart also 50% der Vergleiche. Dafür kommen zusätzliche Vergleiche hinzu: Für jede Ebene, die das Element zunächst zuweit abgesenkt wird, findet ein Vergleich statt (welches der Kinder ist kleiner?), der bei "normalem" Heapsort nicht stattfinden würde. Außerdem muss das Element nach dem Erreichen der untersten Ebene wieder angehoben werden, falls es zu weit unten gelandet ist. Dann muss für jede Ebene, die es zu weit abgesenkt wurde, erneut ein Vergleich durchgeführt werden. Außerdem muss noch ein weiterer Vergleich ausgeführt werden, der den abschließenden aufsteigenden Vorgang abbricht, sobald die richtige Ebene erreicht ist. Wenn ein normales Heapsort-Absinken also 2n Vergleiche benötigt und das Element in der untersten Ebene positioniert werden muss, benötigt BottomUp-Heapsort nur (n+1), also n zum Finden des korrekten Pfades nach unten und einen Vergleich zum Feststellen, dass die unterste Ebene korrekt ist. Wenn es in die zweitunterste Ebene muss, benötigt das normale Verfahren (n-1)*2 Vergleiche und BottomUp benötigt n+1*2+1. So jedenfalls mein Verständnis nach Durchlesen des Artikels.--92.201.51.35 18:58, 21. Okt. 2010 (CEST)