Diskussion:Heapsort

zu kompliziert

Das Verfahren, die dahinterliegende Matematik und die Details sind vielleicht kompliziert, habe jedenfalls nichts verstanden. Könnte man den Artikel nicht wenigstens mit einer Einleitung versehen, die 'für jedermann' - oder zumindest für Leute wie mich (Programmiererfahrung ja, Informatikstudium nein) verständlich sind? (Im Idealfall sollten alle Wikipedia-Artikel nach dem Schema

für 'alle' verständliche Einleitung, dann erst die Details und Fachbegriffe

aufgebaut sein). - Nick B. (nicht signierter Beitrag von 141.52.232.84 (Diskussion | Beiträge) 11:26, 4. Jul. 2003 (CEST))

Man muss auf jeden Fall wissen, was ein Binärer Heap ist. Vielleicht sollte man explizit dranschreiben, dass man zuerst den Artikel Binärer Heap lesen soll. Kompliziert ist es trotzdem, gebe ich zu, ich dachte durch die Beispiele wird es klarer.

Wie eine Einleitung ohne Fachbegriffe aussehen soll, kann ich mir beim besten Willen nicht vorstellen. Vielleicht kriegt das ja jemand anders hin. --Head 11:34, 4. Jul 2003 (CEST)

implementierungen

beispielprogramme

Beispielprogramme sind gut. Ev. auch noch in weiteren Programmiersprachen. (nicht signierter Beitrag von 62.203.10.24 (Diskussion | Beiträge) 00:27, 21. Jul. 2003 (CEST))

Zahl der Beispiel-Implementierungen

Irgendwie finde ich, dass die beispielhaften Implementierungen langsam überhand nehmen. Würde es begrüßen, wenn wir uns auf eine Sprache einigen könnten (im Zweifelsfall eine Beschreibungssprache), anhand der sich der Algorithmus veranschaulichen lässt. --Kasper4711 09:14, 31. Okt. 2006 (CET)

Das ist echt totaler Schmand. Laufzeit vom Quicksort n²? Der hat im Worstcase ne Laufzeit von n*log(n).

Ich habe auch beide Algorithmen implementiert. Quicksort war fast immer schneller. (nicht signierter Beitrag von Lukascho (Diskussion | Beiträge) 15:21, 7. Jul. 2007 (CEST))

unbedingt die beispiele in verschiedenen programmiersprachen drinlassen. anfänger freuen sich, wenn sie den code mal fix reinkopieren können und gleich probieren und sehen, was passiert. was hilfreich wäre zur veranschaulichung wäre sicher noch der pseudocode (nicht signierter Beitrag von Fredfeuerstein (Diskussion | Beiträge) 03:22, 3. Jun. 2008 (CEST))

• Das sehe ich anders, man kann ja ein Link am Ende setzen zu entsprechenden Beispielen in C++ etc. --Wulfgang 14:53, 26. Mai 2009 (CEST)

Java 5 -- Implementierung

Das folgende habe ich erstmal aus dem Artikel entfernt, weil der Code garnicht lauffähig ist. (Zeilennummern und Hihilghts von mir hinzugefügt)

==Java 5== Der beste Sortieralgorithmus mit konstanter Speicherkomplexität und einer Zeitkomplexität von n log n ist der komplizierteste. Er ahmt einen Binärbaum in der zu sortierenden Reihung durch Manipulierung der Indizes nach. Hierbei sind die zwei Nachfolger (im Sinne des Binärbaums) eines Elements mit dem Index i die beiden Elemente mit den Indizes 2i und 2i+1. Falls diese außerhalb der Reihungsgrenzen fallen, hat das Element keine Nachfolger (ist ein Blatt). Die Halde (heap) ist ein Abschnitt der Reihung (zwischen zwei Indizes), die die Haldenbedingung erfüllt. Im Heap Sort wird durch Austausch von Elementen zuerst eine Halde (von hinten nach vorne) aufgebaut und dann (von vorne nach hinten) abgebaut, indem die Spitze der Halde (das größte Element) mit dem hintersten ausgetauscht wird. static class HeapSort<E> extends Comparable<E> { /* die Sequenz innerhalb von sammlung zwischen a und b erfüllt die Haldenbedingung, wenn für jedes i mit 2*i+1 <= b gilt (sofern 2*i und 2*i+1< sammlung.length-1): sammlung[i] > sammlung[2*i] && sammlung[i] > sammlung[2*i+1] */ private void senken(E[] sammlung, int links, int rechts) { /* Die Halde zwischen links und rechts wird durch das Senken des Elements sammlung[links - 1] nach unten erweitert: Die Elemente zwischen links - 1 und rechts bilden eine Halde */ int index = links - 1; // linke Grenze der neuen Halde int nachfolger = 2 * index; // linker Nachfolger final E zuSenken = sammlung[index]; while (true) { // zwei Abbruchstellen if (nachfolger > rechts) break; // weil kein Nachfolger if (nachfolger < rechts && sammlung[nachfolger].compareTo(sammlung[nachfolger + 1]) < 0) // kleineren nachfolger oder nachfolger + 1 auswählen nachfolger ++; if (sammlung[nachfolger].compareTo(zuSenken) < 0) break; // weil Platz gefunden sammlung[index] = sammlung[nachfolger]; // hochrücken index = nachfolger; // nach unten gehen nachfolger = 2 * index; // linker Nachfolger, wenn existiert } sammlung[index] = zuSenken; // Element einfügen } public void heapSort(E[] sammlung) { // sammlung[0] ungenutzt /* Halde aufbauen; die obere Hälfte zwischen sammlung.length/2+1 und sammlung.length-1 erfüllt die Haldenbedingung immer: */ int rechts = sammlung.length-1; for (int links = rechts / 2 + 1; links > 1; links--) { // untere Hälfte einzeln hinzufügen senken(sammlung, links, rechts); // Elemente zwischen 1 und sammlung.length-1 erfüllen die Bedingung // Halde wird abgebaut, d.h. sammlung wird sortiert: final int links = 1; // sammlung[0] ungenutzt for (rechts = sammlung.length-1; rechts > links; rechts--) { // austauschen der äußeren Elemente: final E groesstesElement = sammlung[links]; // Spitze sammlung[links] = sammlung[rechts]; // hinteres Element nach vorne eintauschen sammlung[rechts] = groesstesElement; // Element nach hinten senken(sammlung, links + 1, rechts - 1); // Element senken } } }

1. (Zeile 1): Mit static class HeapSort<E> extends Comparable<E> war wohl eher static class HeapSort<E extends Comparable<E>> gemeint; ansonsten ergibt das keinen Sinn.
2. (Zeile 34): links wird doch gerade durchgezählt!; warum wird es hier noch einmal initialisiert?
3. (Zeile 35): Worauf bezieht sich die Schleife? -- sie wird nie geschlossen!

Ich hab` jetzt leider keine Zeit mich in den Code einzuarbeiten, um das zu korrigieren...

Grüße --Falk _{Sprich^zumir...} 23:03, 21. Jul. 2008 (CEST)

Implementierungen verschieben in die Algorithmensammlung

Hallo, das wurde hier oben schon einmal angesprochen, allerdings ist die Diskussion ein wenig kaputt, daher lieber als eigener Abschnitt. Hier sind ja recht viele Beispielimplementierungen drin, was ja von vielen nicht so gern gesehen ist.

Ich würde die gerne nach

Wikibooks: Algorithmensammlung

verschieben, um ein paar Sprachen erweitern und entsprechend verlinken.

Meinungen dazu?

Ich werde bis zum 22. Juli 2009 auf eine Antwort warten

-- Pberndt _(DS) 15:19, 15. Jul. 2009 (CEST)

Ok dann mach ich das jetzt -- Pberndt _(DS) 17:58, 25. Jul. 2009 (CEST)

gudn tach!

besser zu spaet als gar nicht, moechte ich noch etwas senfen: coole sache! :-) -- seth 18:56, 25. Jul. 2009 (CEST)

Dieser Abschnitt kann archiviert werden. -- Pberndt _(DS) 17:58, 25. Jul. 2009 (CEST)

versinken vs. versickern

Guter Artikel, ich kenne das (lt. Duden Informatik) allerdings als versinken und nicht als versickern. (nicht signierter Beitrag von 82.212.0.37 (Diskussion | Beiträge) 20:13, 9. Jul. 2004 (CEST))

Wenn Objekte in einem mehr flüssigen Element einsinken, dann versinken sie. Ein Wassertropfen hingegen, versickert im Boden. Letzteres passt daher sehr gut, weil sich die kleineren Zahlen in der Array-Wurzel zwischen den größeren Zahlen nach unten bewegen. --Zahlenzauber (Diskussion) 20:57, 11. Jul. 2023 (CEST)

aufsteigend

Die übliche Vorgehensweise ist eigentlich, den Heap aufsteigend anzulegen. In der Wurzel also das kleinste und nicht das größte Element zu haben!! (nicht signierter Beitrag von 80.135.153.237 (Diskussion | Beiträge) 12:01, 11. Jul. 2004 (CEST))

Ist aber zweckmäßig, wenn man den Heap in einem Array aufbaut, dann ist die Wurzel in A[0] und der Heap anfangs der Levelorder, danach wird die Wurzel immer mit dem letzen (aktuellen) Element des Arrays vertauscht. (nicht signierter Beitrag von 82.212.0.37 (Diskussion | Beiträge) 00:14, 31. Jul. 2004 (CEST))

array-beginn bei 1 oder 0

Im Beispiel in der Funktion "heapSort" müssen die Nullen durch Einsen ersetzt werden!?! Ich dachte, wir benutzen ein Array, das bei 1 beginnt... --Kasper (falsch signierter Beitrag von 53.122.197.194 (Diskussion | Beiträge) 10:19, 29. Jun. 2005 (CEST))

In Java (und den meisten anderen Programmiersprachen) beginnen Arrays bei 0. --Head 14:32, 6. Aug 2005 (CEST)

Das ist mir wohl bekannt. Man bekommt aber glaub' Probleme, wenn man mit Index = 0 arbeitet, insbesondere passt da die Berechnung der Nachfolger nicht mehr. Das Array muss dann halt mit max_index+1 deklariert werden, wenn man mit einem verschenkten Slot leben kann. IMHO ist das Beispiel falsch, so wie es dasteht. --Kasper4711 20:42, 6. Aug 2005 (CEST)

Habe das Beispiel jetzt mal korrigiert, nachdem seit langem kein weiterer Einwand gekommen ist. Wer doch vom Gegenteil überzeugt ist, soll mir dann aber bitte erklären, wie man für index == 0 bei nachfolger = 2*index einen Nachfolger des Elements erhält. --Kasper4711 09:52, 6. Feb 2006 (CET)

Zum Beispiel mit index=0 nachfolger = 2*(index+1)-1, nachfolger2 = 2*(index+1) - Ntr0pY (nicht signierter Beitrag von 193.138.91.175 (Diskussion | Beiträge) 11:34, 20. Mär. 2006 (CET))

ACK, das wäre die andere Alternative zur Korrektur gewesen. Ändert aber nix an der Tatsache, dass das Beispiel ursprünglich falsch dastand. --Kasper4711 15:38, 20. Mär 2006 (CET)

Kleine Korrektur, index=0; nachfolger = 2* index +1; nachfolger2=nachfolger+1; Was das alte Beispiel betrifft, kann ich mich nicht dazu äussern, das aktuelle funktioniert. Doch ist es aufgrund der tatsache, dass in allen mir bekannten Sprachen die Arrays mit Index=0 beginnen, dieses Beispiel unbrauchbar. Ich werde demnächst mal ein C++ Beispiel posten, eventuell hilft das ja weiter ;) - Ntr0pY (nicht signierter Beitrag von 88.73.31.54 (Diskussion | Beiträge) 20:00, 20. Mär. 2006 (CET))

Naja, unbrauchbar ist deswegen das Beispiel nicht. Alles eine Frage der Dimensionierung des Arrays, deswegen der Hinweis auf den verschenkten Bucket mit Index=0. --Kasper4711 11:04, 21. Mär 2006 (CET)

aufwand/laufzeit/komplexitaet

unlogisch

Der Satz "Eine vorteilhafte Anordnung von Daten mit mehreren verschiedenen Werten ist prinzipbedingt unmöglich, da dies der Heapcharakteristik widerspricht" scheint mir unlogisch -- oder ich verstehe nicht, was damit gemeint ist. Direkt im nächsten Satz steht doch, dass umgekehrt sortierte Daten den günstigsten Fall darstellen. Wäre das dann nicht eine "vorteilhafte Anordnung"? Oder was ist mit "vorteilhafte Anordnung" anderes gemeint als der günstigste Fall? --217.162.246.68 06:49, 10. Aug. 2024 (CEST)

aufwand

Ist der Aufwand, um den Heap am Anfang aufzubauen nicht nur O(n)? Die Wiederherstellung der Heap-Eigenschaft hat eine Komplexität von O(logn). (nicht signierter Beitrag von 137.226.101.1 (Diskussion | Beiträge) 12:59, 6. Aug. 2005 (CEST))

Der Aufwand für den Aufbau eines initialen Heaps ist O(n). Die Hälfte der Elemente werden einfach eingefügt. Danach verschmelzen immer zwei Heaps zu einem neuen. Bei genauer Abschätzung des Aufwandes ergibt dies O(n). Wenn man aber immer davon ausgeht dass der Aufwand für das Verschmelzen O(log n) ist dann kommt man natürlich auf O(n log n). (nicht signierter Beitrag von 131.220.240.36 (Diskussion | Beiträge) 15:43, 30. Nov. 2005 (CET))

Der Autor hat hier 2 unterschiedliche Worst Case Werte. Einmal O(n*log(n)) (richtig) und O(log(n))(falsch). Ich berichtige das.(mfg Ntr0py) (nicht signierter Beitrag von 193.138.91.175 (Diskussion | Beiträge) 11:00, 3. Mär. 2006 (CET))

laufzeit I

Hallo , mal was zur Laufzeit: "Das Versickern eines Elements von der Wurzel benötigt im ungünstigsten Fall (Worst Case) O(n · log(n)) Schritte." Müssten dass nicht O(log(n)) Schritte sein? Bei einem Aufwand von O(n) zur Erstellung des Heaps frag ich mich wie mann sonst auf O(n log(n)) als Gesamtaufwand kommt... (nicht signierter Beitrag von 84.61.208.162 (Diskussion | Beiträge) 09:54, 10. Apr. 2006 (CEST))

Ja, da bin ich auch der Meinung. Ich ändere das mal... JaK 22:22, 19. Mär. 2007 (CET)

Wie kommt es denn, dass da immernoch O(n · log(n)) steht? Jemand, der sich sicher ist, bitte mal kommentieren oder berichtigen, danke! -- 91.65.229.43 12:23, 5. Dez. 2010 (CET)

Laufzeit II

Im Artikel steht

Für genügend große n (> 16000) ist ein Heapsort im Durchschnitt schneller
als ein optimierter Quicksort. Hinzu kommt das bessere Worst Case-Verhalten
von O(n · log(n)) gegenüber O(n²) beim Quicksort, so dass bei großen 
Sortiermengen Heapsort zu bevorzugen ist.

Das ist sehr zweifelhaft. Vielleicht ist O() von HSort besser, aber bei der Implementation auf dem Computer muss man beachten, daß nicht jeder Zugruff gleich lange dauert, die O()-Notation also nur von begrenztem Wert ist. Ein HSort springt im Gegensatz zu QSort viel mehr im Speicher wahllos hin-und her, verursacht also eine viel größere Menge an Cache-misses. Dadurch ist HSort dann oft doch langsamer als QSort. Daher gibt es viele Fälle, wo dann doch QSort die bessere Wahl ist.

Dazu kommt, daß O(n^2) von QSort keine Bedeutung besitzt. Es ist zwar richtig, aber man kann zeigen, daß dieser Fall bei einem (sinnvollerweise) randomisierten QSort-Algorithmus beliebig unwahrscheinlich wird und für die Praxis nicht relevant ist. (nicht signierter Beitrag von John.constantine (Diskussion | Beiträge) 14:10, 5. Mai 2006 (CEST))

kann jemand das mit 16000 untermauern? 16000 klingt ein bisschen wenig! (nicht signierter Beitrag von 88.70.9.33 (Diskussion | Beiträge) 14:47, 24. Jul. 2006 (CEST))

laufzeit/verstaendlichkeit

Also ich finde es wesentlich verständlicher, wenn als Laufzeit "O(n + n log(n)) = O(n log(n))" angegeben wird. Denn der initiale Aufbau des Heaps kostet O(n). Danach muss für jedes Element (Wurzel), das man aus dem Heap entfernt Heapify (Wiederherstellung der Heap-Eigenschaft) O(log(n)) aufgerufen werden. Daher kommt O(n log(n)). Das hat ja im Prinzip nichts mehr mit der Laufzeit für den Aufbau des Heaps zu tun. Die fällt nicht mehr ins Gewicht. --88.72.236.68 00:20, 23. Jul. 2007 (CEST)

Heapsort und Komplexität

In diesem Artikel wird immer wieder etwas in der Komplexitätsbetrachtung falsch gemacht. Ich habe die Laufzeiten korrigiert. Insgesamt wirkt dieser Artikel als ob der Text nicht wirklich zu den theoretischen Grundlagen passt. (nicht signierter Beitrag von 84.63.0.237 (Diskussion | Beiträge) 22:30, 3. Mai 2006 (CEST))

zu sortierende symbole

ich finde den artikel recht lesbar, allerdings ist für mich die verwendung von buchstaben statt zahlen als zu sortierende elemente weniger intuitiv... falls es nicht nur mir so geht sollte das geändert werden -- wizzar 07:37, 19. Dez 2005 (CET)

Habe prinzipiell nichts dagegen einzuwenden, allerdings fällt dann evtl. die Unterscheidung zu den Indices schwieriger („Nummer 3 auf Position 5“ etc.). --Kasper4711 08:39, 19. Dez 2005 (CET)

Finde die Buchstaben ok. Ist sicher etwas weniger intuitiv als Zahlen, aber da Heapsort eh nicht auf einen Blick verstanden wird macht das nix :) -NtropY (nicht signierter Beitrag von 88.73.31.54 (Diskussion | Beiträge) 20:00, 20. Mär. 2006 (CET))

kleiner fehler in beispiel

S P R E H O A|T Wir versickern E nicht weiter, denn S ist bereits an der ^ ^ richtigen Position. Stattdessen vertauschen wir S und A.

Ich glaube es sollte eher "...,den T ist bereits an der richtigen Position" heißen, weil das der Grund ist, wieso E nicht weiter versickern kann. Ich ändere das ganze einfach mal... (nicht signierter Beitrag von 84.165.9.12 (Diskussion | Beiträge) 18:23, 17. Feb. 2006 (CET))

heap -> max-heap

Hallo, ich habe in dem Beispiel den Begriff "heap" in den Begriff "max-heap" geändert, da das präziser ist. ich hoffe ich hatte recht. noch schöner fände ich es, wenn das beispiel sich an einem min-heap orientieren würde, ich kann nämlich besser vorwärts buchstabieren als rückwärts :)

und noch was zum beispiel des heap-sortierens: da steht immer "x mit y vertauschen"... das klingt so, als wenn der "größere" buchstabe noch für den heap relevant wäre, aber das ist es ja nicht mehr, er kann ja bereits rausgenommen werden.

danke, --Abdull 22:48, 4. Mär 2006 (CET)

vergleich mit quicksort

Gibt es irgendwo eine Quellenangabe zum Vergleich mit Quicksort? Ich kann mir das nicht ganz vorstellen - aufgrund des Cache-Verhaltens muss gerade bei n > 16000 Quicksort schneller sein.

CornedBee (nicht richtig signierter Beitrag von CornedBee (Diskussion | Beiträge) 22:14, 26. Apr. 2006 (CEST))

Da muss ich Dir zustimmen. Quicksort ist grundsätzlich immer schneller als Heapsort. Ich habe mir auf YouTube ein Video angesehen, wo 16 Sortierverfahren in 4 verschiedenen Datenstrukturen gegeneinander angetreten sind. Quicksort war immer schneller als Heapsort.

---- 1. Zufallszahlen ----

Quicksort: 9 Sekunden (30,7% schneller als Heapsort)

Heapsort: 13 Sekunden

---- 2. gemischte Balkentreppe ----

Quicksort: 3 Sekunden (76,9% schneller als Heapsort)

Heapsort: 13 Sekunden

---- 3. Worst-Case ----

Quicksort: 6 Sekunden (70,0% schneller als Heapsort)

Heapsort: 20 Sekunden

---- 4. Best-Case ----

Quicksort: 5 Sekunden (75,0% schneller als Heapsort)

Heapsort: 20 Sekunden

--Zahlenzauber (Diskussion) 15:52, 29. Dez. 2023 (CET)

Noch etwas:

1. Je größer die Anzahl der zu sortierenden Elemente wird, umso schneller wird Quicksort im Vergleich zu Heapsort.

2. Würde man das versickern des nach vorne getauschten Elementes weglassen und anstelle dessen die ganze Wurzel im Array von hinten nach vorne immer nur aktualisieren, ohne fehlerhafte untere Heaps zu reparieren, dann hätte Heapsort die gleiche Anzahl von Vergleichen und Vertauschungen wie Bubblesort. Bubblesort würde dann sogar minimal schneller sortieren. --Zahlenzauber (Diskussion) 14:46, 31. Dez. 2023 (CET)

Heapsort im Vergleich mit 23 anderen Sortierverfahren

Ich möchte noch hinzufügen, dass Heapsort eher zu den langsamen Sortierverfahren zählt. In einem anderen Video hat man 24 Sortierverfahren gegeneinander antreten lassen, um ein zufällig gemischtes Array zu sortieren. Heapsort erreichte dabei nur Platz 16.

Platz 1: Radixsort (LSD) (12 Sekunden)

Platz 2: Radixsort (MSD) (16 Sekunden)

Platz 3: Quicksort (dual pivot) (17 Sekunden)

Platz 4: Quicksort (ternary, L R ptrs) (18 Sekunden)

Platz 5: Quicksort (L R ptrs) (21 Sekunden)

Platz 6: Quicksort (L L ptrs) (22 Sekunden)

Platz 7: Quicksort (ternary, L L ptrs) (23 Sekunden)

Platz 8: Tim Sort (25 Sekunden)

Platz 9: Shell Sort (26 Sekunden)

Platz 10: std::sort (gcc) (26 Sekunden)

Platz 11: Merge Sort (27 Sekunden)

Platz 15: Smooth Sort (37 Sekunden)

Platz 13: Block Merge Sort (WikiSort) (38 Sekunden)

Platz 14: Comb Sort (39 Sekunden)

Platz 15: Bitonic Sort (42 Sekunden)

Platz 16: Heapsort (43 Sekunden)

Platz 17: Binary Insertion Sort (51 Sekunden)

Platz 18: Insertion Sort (60 Sekunden)

Platz 19: Selection Sort (79 Sekunden)

Platz 20: Coktail Shacker Sort (83 Sekunden)

Platz 21: Gnome Sort (103 Sekunden)

Platz 22: Cycle Sort (112 Sekunden)

Platz 23: Bubble Sort (119 Sekunden)

Platz 24: Odd-Even Sort (122 Sekunden)

--Zahlenzauber (Diskussion) 15:55, 29. Dez. 2023 (CET)

quicksort worstcase

So ein Käse, Quicksort hat worstcase n²! --84.150.200.185 12:18, 16. Jul. 2008 (CEST)

Nein, kein Käse. Quicksort ist im Worst-Case 70% schneller als Heapsort. --Zahlenzauber (Diskussion) 15:06, 29. Dez. 2023 (CET)

prinzip der sortierung inkonsistent mit beispiel

Kann es sein, das "Prinzip der Sortierung" und das "Beispiel mit Zahlen" nicht übereinstimmen. Sollte man vielleicht dazuschreiben. Da das Beispiel mit Zahlen ja absteigend sortiert, vorher aber von aufsteigend die Rede ist. Der Artikel an sich ist aber richtig gut zu verstehen. Gefällt mir. (nicht signierter Beitrag von 85.179.137.76 (Diskussion | Beiträge) 13:56, 18. Sep. 2007 (CEST))

Array zum Heap machen

"Man beachte, dass für die zweite Hälfte jedes Arrays die Heap-Eigenschaft bereits erfüllt ist, denn jeder Knoten in der zweiten Hälfte des Arrays entspricht im Heap einem Blatt, hat also keinen Nachfolgeknoten, dessen Wert größer sein könnte als der eigene (im Folgenden wird der Einfachheit halber der Knoten mit dem größten Wert der „größte Knoten“ genannt)."

Das ist doch schon wieder Käse! Das kann man so nun wirklich nicht sagen, denn immerhin haben die Knoten aus der hinteren Hälfte Vorgängerknoten, und die Knoten müssen auch mit diesen Knoten in der Heapbedingung: Kinder>Eltern, genügen.

Habe ich zB das Array: 4,3,2,1 dann gilt doch für 2 und 1 nicht die (Min-)Heapbedingung, weil sie kleiner sind als ihre Eltern! Denn der MinHeap zu dem Array lautet: 1, 2, 3, 4. Und wo ist jetzt die zweite Hälfte gleich?

Ich weiß nicht, der Satz ist nicht mal einfach nur schlecht formuliert oder so, sondern macht einfach keinen Sinn, ich wäre dafür ihn ersatzlos zu streichen.

IMHO kann man einen Heap nur so machen, indem man aus einem unsortierten Array kontinuierlich extractMin ausführt. BZW eben einen Sortieralgorithmus laufen lässt und dann einfach den Heap konstruiert.

--84.150.200.185 12:23, 16. Jul. 2008 (CEST)

beispielbild fehlerhaft

Im Beispielbild "Heapsort.png" ist meiner Meinung nach ein kleiner Fehler. Direkt nach der Bildung des Heaps sind die Kinder von 18 falschherum. Wenn man von hinten einliest ergibt sich die 8 als rechtes Kind, hier ist es leider das linke. (nicht signierter Beitrag von 78.34.131.42 (Diskussion | Beiträge) 19:57, 4. Aug. 2008 (CEST))

Ich komme auf das gleiche Ergebnis. 6 und 8 müssen in der Grafik zu Beginn vertauscht werden. -- Schmidt.Andre 16:43, 5. Aug. 2009 (CEST)

Der Fehler besteht immer noch und sollte mal gefixt werden. Oder das Beispiel dann um "Heapify" erweitert werden, so dass man den Weg zum Heap auch nachvollziehen kann. (nicht signierter Beitrag von 87.139.191.81 (Diskussion) 10:28, 29. Okt. 2012 (CET))

--- Push ---

Auch nach meinen Berechnungen ist an dieser Stelle ein Fehler. Sollte unbedingt gefixt werden. (nicht signierter Beitrag von 2003:5D:F4C:5365:A948:8D4D:883B:345A (Diskussion | Beiträge) 14:22, 8. Jun. 2014 (CEST))

Zur Bildunterschrift: "Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen Sortierschritt kurz eingeblendet wird" --> "Der Algorithmus besteht aus zwei Schritten. In einem ersten, vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet (dessen Baumstruktur wird kurz eingeblendet). In einem zweiten Schritt findet das eigentliche Sortieren statt. (nicht signierter Beitrag von Xx010101 (Diskussion | Beiträge) 21:54, 7. Aug. 2009 (CEST))

Ich muss hier zustimmen, die Kinder der "18" sind beide falsch herum. Die "6" muss sich links und die "8" rechts befinden. --Zahlenzauber (Diskussion) 05:35, 29. Dez. 2023 (CET)

Ich habe die Fehler mit der "6" und "8", sowie einem Tausch-Pfeil, der zu viel platziert wurde, zwar beheben können, allerdings kann ich die "reparierte Grafik" nicht hochladen, weil ich feststellen musste, dass es sich beim Original um das Werk eines anderen Nutzers handelt (Urheberrecht). Ich habe den betreffenden Nutzer angeschrieben und ihm angeboten, ihm die reparierte Grafik zur Prüfung per E-Mail zuzusenden. Warten wir die Antwort ab. Wenn er die Grafik übernimmt, dann werden sich die Fehler von alleine beheben. --Zahlenzauber (Diskussion) 17:19, 29. Dez. 2023 (CET)

Wir reden über dieses Bild, oder? Das kannst du problemlos überschreiben oder als neues Bild hochladen, solange du es unter einer kompatiblen Lizenz veröffentlichst und den Urheber nennst. --Dexxor (Diskussion) 17:01, 30. Dez. 2023 (CET)

Ja, genau um dieses Bild geht es. Muss ich es nur unter dem gleichen Namen hochladen, oder wie würde das gehen? Ein Problem besteht noch darin, dass ich mit meinem Programm unter PNG keine transparenten Farben erzeugen kann, wie beim Original. --Zahlenzauber (Diskussion) 01:45, 31. Dez. 2023 (CET)

Wenn du nach unten scrollst, findest du den Link Eine neue Version dieser Datei hochladen. Dort solltest du aber kein PNG, sondern ein SVG hochladen. SVG hat den Vorteil, dass man es mit Inkscape leicht bearbeiten kann. --Dexxor (Diskussion) 09:53, 31. Dez. 2023 (CET)

Tut mir leid, ich habe leider nur "Paint" auf meinem Computer. --Zahlenzauber (Diskussion) 14:33, 31. Dez. 2023 (CET)

Aber ich könnte auch mit Excel eine neue Grafik erstellen, bei der alle Schritte in einer Tabelle angeordnet sind. Das dürfte dann wohl auch besser verständlich sein. Dafür würde ich dann auch andere Zahlen verwenden. --Zahlenzauber (Diskussion) 14:37, 31. Dez. 2023 (CET)

Sortieren vs. Erstellen des Max-Heap

Ich finde den Artikel sehr missverständlich.

Es klingt so als wäre es die Hauptfunktion des Heap-Sorts einen Max-Heap zu erstellen. Die eigentliche Funktion des Algorithmus, nämlich eine aufsteigende Sortierung wird überhaupt nicht erwähnt. Stattdessen wird in den Beispielen davon ausgegangen, dass diese Aufgabenstellung klar ist.

Ich denke in einem Artikel über einen Algorithmus, sollte vor allem stehen, was dieser Algorithmus tut und nicht nur was sein Teilalgorithmus macht. Man könnte z.B. den Text unter der Animation in den eigentlichen Text einfügen - ohne diesen hätte ich überhaupt nicht verstanden, wie der HeapSort funktioniert. (nicht signierter Beitrag von Tyru (Diskussion | Beiträge) 01:18, 24. Feb. 2010 (CET))

---

Zitat: "Den Rest des Arrays muss man wieder in einen Max-Heap überführen, indem man das erste Element versickern lässt." Die Überführung in einen Max-Heap ist also elementarer Bestandteil des Algorithmus. Wenn man das weglässt, sieht der artikel so aus: Man überführt die Liste in einen Maxheap und vertauscht das erste mit dem letzten element. Das wiederholt man. Und daraus wird man dann schlau?--212.79.180.27 18:15, 19. Mai 2011 (CEST)

Abschnitt: Beispiel für die Überführung in einen Max-Heap

Hallo euch Artikelautoren. Großes Lob an euch für den gesamten Artikel. Man erkennt, dass ihr versucht, einen Spezialbegriff auch einem Laien verständlich zu erklären. Beispiele eignen sich dafür sehr gut! Ich bin Fast-Laie. Leider kann ich den Anfang vom 2. Schritt in diesem Beispiel „Wir fahren mit dem A fort.“ nicht nachvollziehen. Wieso fahren wir gerade mit „A“ fort? Komm ich leider nicht mit. Wenn ihr denkt, dass das auch anderen so gehen könnte, dann ergänzt doch bitte eine kurze Begründung, warum man beim 2. Schritt A wählt. Beste Grüße --W like wiki 20:15, 21. Jun. 2010 (CEST)

PS.: Es scheint ja so zu sein, das man die Knoten von unten "nach oben" "hinaufmarschiert". Und es scheint mir auch, als wenn es eine mathem Prinzip(Regel) gibt, nachdem die im ersten Schritt beschriebene "Mitte" in der Reihe(Wort) auch IMMER der "unterste" Knoten im Baum ist. Vielleicht könnte man dieses (mir leider unbekannte) Prinzip erwähnen. Dann erklären sich vielleicht die nächsten Schritte besser. Wenn es dieses Prinzip nicht geben sollte, dann könnte man vielleicht darauf hinweisen, dass in diesem Beispiel die Mitte P im Wort zufällig auch der unterste Knoten ist. Oder dann besser ein anderes Beispiel wählen. Grüße--W like wiki 20:34, 21. Jun. 2010 (CEST)

PS.: Könnte man diesen Satz: Um die Rechnung zu vereinfachen, wird im Folgenden vorausgesetzt, dass das erste Element des Arrays den Index 1 hat. Die Nachfolger eines Knotens mit dem Index i liegen dann an den Positionen 2·i und 2·i+1. etwas laienverständlicher schreiben. Vielleicht reicht auch schon ein Wikilink zu einem Artikel, der diesen speziellen Index und die Notation 2·i erklärt.--W like wiki 20:58, 21. Jun. 2010 (CEST)

Wer das Wort Array kennt, müsste auch wissen, was dort ein Index ist. Ein passender Wikilink zu Index (Mathematik) wäre aber trotzdem möglich. Aber dass du die Notation 2·i nicht verstehst, kaufe ich dir nicht ab. Der ganze Sachverhalt könnte allerdings besser erklärt werden, vielleicht aber ausführlicher an einer zentralen Stelle, zum Beispiel im Artikel Repräsentation von Graphen im Computer in einem neuen Abschnitt über Bäume. --Zahnradzacken 14:17, 22. Jun. 2010 (CEST)

Hallo Zahnradzacken, hmmm...Multiplikation. Lustig, manchmal erkennt man das naheliegendste nicht. War davor wahrscheinlich auf zuviel anderen Mathematik-Artikeln gewesen, die dann immer schnell in mir exotisch erscheinende spezielle Notationen übergehen. Habe werde die Links mal in die Seite so einbauen. PS.: Es bleibt noch die Frage, wie würde die Überführung in ein Max-Heap vorsichgehen, wenn es ein 9-buchstabiges Wort wäre HEAPSORTO zB :)? Dann hätte könnte man im ersten Schritt das S mit keinem Nachfolger vergleichen. Vergleicht man es dann mit seinem Vorgänger oder geht man gleich zum nächsten Knoten P? --W like wiki 00:58, 23. Jun. 2010 (CEST)

Hallo zusammen, mir ist am Ende erst aufgefallen das es sich bei der Übertragung in ein Array ja um eine Levelorder-Traversierung handelt. Vielleicht könnte man dies als Grundlage nehmen um die Array-Abbildung deutlicher zu machen?! (ist eventuell etwas intuitiver zu verstehen) Ist nur ne idee die mir gerade spontan beim durchlesen gekommen ist. --[Gast] 13:17 Jun. 2010 (nicht signierter Beitrag von 128.176.237.227 (Diskussion) 13:18, 18. Jul 2010 (CEST))

Ich glaube dass das Hauptproblem beim Verstehen dieses Abschnitts die Art und Weise wie hier ein Binärbaum in einem Array gespeichert wird ist. Die optimale Lösung hierfür wäre mMn eine Verlinkung auf Binärbaum#Suchen_per_Index. Eventuell sollte man diesen Abschnitt im Binärbaumartikel noch etwas ausführlicher und anschaulicher gestalten und dort erklären warum a[2*i] das linke Kind von a[i] ist. --Enormator 13:28, 27. Jan. 2011 (CET)

Das Problem, dass der Zusammenhang zwischen Baum und Array nicht klar wird, könnte auch ganz gut durch eine animierte Graphik behoben werden, die klar macht, welche Elemente des Arrays welchen Elementen des Baums zugeordnet werden. Das Sieht man eigentlich schon ganz gut durch die "Balken" im Array, steht ja auch darüber, was die bedeuten. Würde man den Array und den Baum in einer Animation zeigen, würde das vielleicht übersichtlicher für die, denen das so immernoch nicht klar wird. Oder es genügt schon, wenn man die Zwischenschritte der Überführung nicht nur als Liste sondern auch im Baum zeigt. Könnte sich ja mal bei Gelegenheit ein kreativer Mensch dranbegeben, ich bin gerade im Lernstress und habe für solche Spielereien keine Zeit. --212.79.180.27 17:25, 19. Mai 2011 (CEST)

Besseres Beispielbild

Ich habe mit Excel eine - wie ich finde - verbesserte grafische Darstellung der Funktionsweise von Heapsort erstellt. Daher würde ich gerne mal nachfragen, ob Ihr ebenfalls der Meinung seid, dass man das aktuelle Beispielbild im Artikel durch meines Ersetzen und den Text entsprechend anpassen sollte? Wenn ich an den Texten in der Grafik etwas ändern soll, dann kann ich das natürlich sehr schnell machen.

--Zahlenzauber (Diskussion) 14:17, 24. Mär. 2024 (CET)