Diskussion:Heapsort

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

Habe in anderer Quelle einen Worst Case von O(n*log(n)) gefunden. Habe auch nur danach gesucht weil ein Worst Case O(log(n)) doch sehr unwahrscheinlich ist. (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)

ich finde den artikel recht lesbar, allerdings ist für mich die verwendung 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)