Diskussion:Heap (Datenstruktur)

Erster Abschnitt: Was spricht gegen den Link nach Deap?

@Coma: ein link auf Deap ist okay, finde ich -- was spricht dagegen, den Artikel zu verlinken? --Pinguin.tk 12:52, 23. Sep 2004 (CEST)

Dagegen spricht, dass ich Deaps nicht kenne. Wenn es sie überhaupt gibt (Google liefert lediglich Einträge auf Wikipedia und Ableger), dann ist der entsprechende Artikel dazu so schlecht, dass er völlig unbrauchbar ist. Aufgrund dieser Unbekanntheit, kann man ihn auch nicht in Datenstruktur in die Liste der wichtigen Datenstrukturen einordnen (und schon garnicht zwischen Binomial- und Fibonacci-Heaps). --Coma 16:01, 23. Sep 2004 (CEST)

hmm okay, ich dachte zwar, den Begriff schon mal gehört zu haben, hab ihn jetzt aber auch in keinem Algorithmen/Datenstrukturen-Buch gefunden... aber vielleicht sollte man trotzdem mal versuchen herauszubekommen, ob es sowas überhaupt gibt, oder ob man den Artikel nicht lieber löschen sollte! --Pinguin.tk 16:37, 23. Sep 2004 (CEST)

Ich hab es jetzt nur als Doppelheap mit Abkürzung Deap gefunden und entsprechend den Inhalt geändert. --Coma 17:39, 23. Sep 2004 (CEST)

ich hab nochmal gesucht und ein paar websites zu Deaps gefunden, scheint es doch zu geben, wenn auch vielleicht nicht so sehr verbreitet:

• http://portal.acm.org/citation.cfm?id=33331
• www.uni-protokolle.de/Lexikon/Deap.html
• http://www.brpreiss.com/books/opus5/javadoc/Opus5/Deap.html

--Pinguin.tk 18:52, 23. Sep 2004 (CEST)

Der Link zu Uni-Protokolle ist eine Wikipedia-Kopie! Die anderen sagen das selbe wie ich. Insofern sind meine Änderungen also korrekt. --Coma 20:03, 23. Sep 2004 (CEST)

ich wollte damit ja auch gar nicht sagen, dass Du Unrecht hast, sondern nur, dass der Begriff "Deap" tatsächlich so verwendet wird... --Pinguin.tk 20:22, 23. Sep 2004 (CEST)

Ja, ich wollte auch nur ausdrücken, dass die Links (bis auf den mittleren) noch mal einen gute Bestätigung waren. Vielen Dank. --Coma 22:33, 23. Sep 2004 (CEST)

dann ist ja gut :)

Da aber die Existenz des Deaps/Doppelheaps nun einigermaßen geklärt ist, meinst Du nicht, dass man ihn doch wieder von diesem Artikel aus verlinken kann bzw. sollte? --Pinguin.tk 15:17, 24. Sep 2004 (CEST)

Hab ich erledigt! --Coma 15:33, 24. Sep 2004 (CEST)

super, danke! --Pinguin.tk 17:00, 24. Sep 2004 (CEST)

Laufzeit von extract-Min bei binären Heaps

Mit extract-Min ist soweit ich weiß sowohl die Rückgabe des Heapminimums als auch die Löschung desselben aus dem Heap verbunden. Dieses Löschen braucht aber mindestens O(log n).
(Der vorstehende Beitrag stammt von Jvitense (Beiträge) – 15:34, 29. Jan. 2007 (MEZ) – und wurde nachträglich unterschrieben.)

das ist richtig, danke für die korrektur. --Koethnig 18:53, 29. Jan. 2007 (CET)

Radix Heaps

warum nicht?! -> [1]
--bastian
(Der vorstehende Beitrag stammt von 131.159.0.7 – 10:50, 2. Mär. 2007 (MEZ) – und wurde nachträglich vollständig – mit Zeitangabe – unterschrieben.)

Laufzeiten

die laufzeitangaben sind nicht konsistent mit denen der artikel über die einzelnen umsetzungen! (z.B. worst-case delete bei fibonacci-heap)
--bastian
(Der vorstehende Beitrag stammt von 131.159.0.7 – 11:57, 2. Mär. 2007 (MEZ) – und wurde nachträglich vollständig – mit Zeitangabe – unterschrieben.)

Ich weiß zwar nicht, was ein Pairing Heap ist, aber die Laufzeiten müssen falsch sein. Mit Insert und Extract Min in $O(1)$ könnte man einen vergleichsbasierten Sortieralgorithmus in $O(n)$ implementieren, was bekannterweise nicht möglich ist. Mindestens eins von beiden muss in $\Omega (\log(n))$ liegen. Das Gleiche gilt für Leftist Heaps, wobei ich an dieser Stelle auch das "or" in den Laufzeiten nicht verstehe. Gibt es irgendwo Quellen über diese Heaps, am Besten mit Beweisen für Korrektheit und Laufzeit? --Morgurth 18:55, 15. Nov. 2007 (CET)

In dem Paper The Pairing Heap: A New Form of Self-Adjusting Heap werden Paired Heaps beschrieben. Die Autoren vermuten amortisierte Laufzeiten von $O(\log(n))$ für delete-min und delete, und konstante Laufzeiten für alle anderen Operationen, konnten aber nur für make heap und find min konstante Laufzeiten beweisen, und logarithmische für alle anderen. Was in der Tabelle steht, ist jedenfalls so oder so Unfug. Ich werde das mal ändern. Möchte vielleicht noch jemand anders etwas fundiertes über Leftist Heaps suchen? --Morgurth 17:39, 24. Nov. 2007 (CET)

Totale Ordnung/kleiner-Relation über ganzen Zahlen

"Über die Menge der Schlüssel muss daher eine totale Ordnung festgelegt sein, über welche die Reihenfolge der eingefügten Elemente festgelegt wird. Beispielsweise könnte die Menge der ganzen Zahlen zusammen mit der Kleiner-Relation (<) als Schlüssel-Menge fungieren."
Wenn ich mich nicht täusche, müsste da "Kleiner-Gleich-Relation (≤)" stehen, damit die Ordnung total (d.h. insbesondere alternativ) ist?
(Der vorstehende Beitrag stammt von 80.141.82.42 – 16:41, 5. Dez. 2007 (MEZ) – und wurde nachträglich unterschrieben.)

Neuer Weblink

Ich wollte meine Seite mit animierten Darstellungen vom Heap (http://www.chrislaux.com/de/heap.html) für die Weblinks Sektion anbieten. Die Erklärungen sind dort alle auf Deutsch und die Animationen ergänzen den Text dieser Wikipedia-Seite gut.

--Ctlaux (Diskussion) 21:23, 3. Sep. 2019 (CEST)

C++ Code leaks memory

Der C++ Code produziert verwaisten Speicher. Speicher für das Feld "elements" wird nur allokiert, nicht wieder freigegeben.

 elements = new int[capacity];

Empfehlenswert ist die Nutzung von RAII [2], d.h. z.b. ein std::unique_ptr<int>. Weiterhin scheinen die Kommentare auf der Urpsrungsseite darauf hin zu weisen dass der Code fehlerhaft ist.

Abhängig von der Intention ist auch die Nutzung von std::make_heap aus <algorithm> der std-library möglich, welches die Implementation vereinfachen sollte. --132.180.238.55 14:36, 16. Feb. 2023 (CET)