Diskussion:Heapsort

aus Wikipedia, der freien Enzyklopädie

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

---

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...

---

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

---

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...

---

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).

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)

---

WOO HOO! :)  
Artikel Nr. 20000 :D  
gute Nacht... --Head 05:24, 4. Jul 2003 (CEST)

---

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).

---

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.

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)

---

Beispielprogramme sind gut. Ev. auch noch in weiteren Programmiersprachen.

---

Guter Artikel, ich kenne das (lt. Duden Informatik) allerdings als versinken und nicht als versickern.

---

Die übliche Vorgehensweise ist eigentlich, den Heap aufsteigend anzulegen. In der Wurzel also das kleinste und nicht das größte Element zu haben!!

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.

---

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

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

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

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)

---

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

Inhaltsverzeichnis 1 heap -> max-heap 2 Heapsort und Komplexität 2.1 Laufzeit 3 Zahl der Beispiel-Implementierungen

[Bearbeiten] 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)

[Bearbeiten] 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.

[Bearbeiten] Laufzeit

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.

–kann jemand das mit 16000 untermauern? 16000 klingt ein bisschen wenig!

[Bearbeiten] 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)