Diskussion:Binärer Heap

Root

In der Wikipedia steht anscheinend nirgends etwas darüber, was die Wurzel eines Baums ist.

Aktuell schon - z.B. bei Binärbaum. --Gms 17:54, 6. Feb. 2012 (CET)

Build

Über den Algorithmus, mit dem man ein Array in einen Heap umwandelt, habe ich noch nichts geschrieben. --Head 11:44, 23. Jun 2003 (CEST)

Habe es inzwischen ergänzt. --Gms 17:54, 6. Feb. 2012 (CET)

Partielle Ordnung

Ich finde, es sollte noch daraufhingewiesen werden, das in einem Heap keine totale Ordnung vorherrscht, obwohl die Schlüssel natürlich eine totale Ordnungsrelation besitzen müssen. Auf jeden Fall gibt es aber eine partielle Ordnung.

Wird aktuell in Heap (Datenstruktur) und Binärbaum#Partiell geordneter Baum entsprechend darauf hingewiesen. --Gms 17:54, 6. Feb. 2012 (CET)

Index/Kinder

Zum o.g. Algorithmus: Die Elemente an array[2*i] und array[2*i + 1] sind - sofern sie nicht ausserhalb der Array-Grenzen liegen, die Söhne/Kinder eines Knotens mit Index i.

Ist nun Teil des Artikels. --Gms 17:54, 6. Feb. 2012 (CET)

Im Artikel richtig - hier falsch: Die Kinder von [0] sind nicht [0] und [1].

--arilou (Diskussion) 15:38, 8. Jan. 2019 (CET)

Heapify Phasen

Zudem: Man kann heapify() auch getrennt als HeapDown() und HeapUp() implementieren, da Delete() und Replace() nur HeapDown() und Insert() nur HeapUp() benötigt. -- M. Moll 19.09.2005

Heapify ist nun aus den genannten Gründen bzw. der Darstellung in der einschlägigen Literatur, einphasig definiert - HeapUp entspricht 'decreaseKey' im aktuellen Artikel. --Gms 17:54, 6. Feb. 2012 (CET)

Heap in einem Array speichern

Hallo!

Wäre es nicht sinnvoller zu sagen, dass das Array an Position 0 beginnt und dann die children bei 2i+1 und 2i+2 liegen? Ich finds sinnvoller, da schlißlich in den meisten (oder sogar allen?) Programmiersprachen Array mit dem Index 0 beginnen. -- M. Krickl 4.4.2006

Dem Laien müsste das erklärt werden. Ich habs jetzt so geändert, das im Prinzip beides drin steht, ohne es explizit zu erwähnen. Die erste Position ist in solchen Programmiersprachen ja die Position mit dem Index 0 usw. ... -12:40, 4. Apr 2006 (CEST)

Nun wird beides explizit erwähnt und Pseudo-Code abstrahiert von der Index-Funktion. --Gms 17:54, 6. Feb. 2012 (CET)

Suchen bzw. Zugriff auf Elemente

Eins ist mir noch nicht ganz klar: wenn ich den Schlüssel habe, kann ich damit dann auch sofort auf das Element zugreifen? Falls dem nicht so ist, stellt sich für mich die Frage, wie ich Elemente effizient suchen kann, da ich ja im schlimmsten Fall den ganzen Heap durchsuchen müsste. --Daniel Mex 17:10, 29. Sep. 2007 (CEST)

Ich denke, bei remove und changeKey wird der Index (oder Zeiger, je nach Implementierung) des Elements übergeben. Anschließend braucht man O(log n) Schritte, um die Heapeigenschaft wieder herzustellen. Anders kann ich es mir nicht vorstellen, weil der Heap ja kein Suchbaum ist und man wie du schon sagtest mit Pech den ganzen Heap durchlaufen muss.

Ich denke die Einleitung sagt deutlich, wozu der Heap gut ist. Dort steht nicht(!), dass man ein Element im Heap effizient suchen kann! Das ist einfach nicht die Aufgabe dieser Datenstruktur. Im übrigen steht das auch nochmal explizit unter "Bemerkungen". Der Schlüssel dient nicht zum suchen, sondern zum Festlegen der Priorität. Im Normalfall wird das einfach eine Zahl sein! --Koethnig 02:51, 15. Okt. 2007 (CEST)

Du hast recht: die Einleitung sagt deutlich, wozu der Heap gut ist. Weiter unten steht aber, dass der Heap effizient die Operation remove unterstützt und an dieser Stelle wird meiner Meinung nach ein bisschen gemogelt, denn bevor ich ein Element löschen kann, muss ich wissen, wo es sich befindet. In anderen Datenstrukturen wird das Suchen oft als Teil des Löschens gesehen, hier gehen wir dagegen einfach davon aus, dass wir schon wissen, wo das Element gespeichert ist. Die Folge ist, dass sich die Laufzeit log n nicht mit der Löschen-Laufzeit anderer Datenstrukturen vergleichen lässt. --Daniel Mex 11:15, 15. Okt. 2007 (CEST)

Von welcher Art Heap wind in den Abschnitten "Struktur" und "Implementation der Operationen" gesprochen?

Wenn ich das jetzt nicht falsch verstehe, wird im Abschnitt "Struktur" vom Max-Heap gesprochen und im Abschnitt "Implementation der Operationen" vom Min-Heap. Das ist verwirrend. Der Hinweis, dass es einen Min- und einen Max-Heap gibt, sollte vorher stehen und es sollte in den beiden Abschnitten klar sein wovon gesprochen wird.

Berechtigter Einwand. Ich habe nun die Erläuterungen auf dem Min-Heap beschränkt und darauf hingewiesen, daß es bei Max-Heaps analog aussieht. --Sulai 16:33, 12. Jan. 2008 (CET)

Heapify Algorithmus

heapify() enthält einen entscheidenden Fehler, da die Kindknoten untereinander nicht verglichen werden. Im Beispielbaum (oben auf der Seite) würde ein remove(H,0) dazu führen, dass 12 in die Wurzel verschoben, anschließend heapify() aufgerufen wird. In heapify() wird die 12 zunächst mit dem linken Kindknoten (=2) verglichen, anschließend jedoch wg. 3 < 12 der rechte Knoten (=3) ausgewählt. Das anschließende swap führt dazu, dass 3 in die Wurzel verschoben wird und somit die Heapbedingung verletzt. (nicht signierter Beitrag von 178.27.198.60 (Diskussion) 13:04, 7. Mär. 2012 (CET))

Stimmt nicht, da beim Vergleich 12 mit 2 die Variable x auf den Index vom linken Kindknoten gesetzt wird und deshalb der rechte Knoten dann nicht mit 12 sondern mit 2 verglichen wird. (nicht signierter Beitrag von 80.109.198.231 (Diskussion) 23:25, 10. Apr. 2013 (CEST))

Remove

Die Remove Funktion ist falsch. Je nachdem welchen Wert das letzte Element im Heap hat, der an die Stelle des gelöschten Elements verschoben wird, muss entweder heapify oder auch heapifyUp / decreaseKey (fehlt im Code) aufgerufen werden.

Beispiel Heap bei dem die Remove Funktion nicht richtig funktioniert: Heap: 1,7,3,15,10,5 Lösche das Element mit Wert 10, danach sollten wir diesen Heap haben: 1,5,3,15,7

Die Remove Funktion benutzt aber nur heapify, wodurch wir dies erhalten (ist kein Heap mehr): 1,7,3,15,5 (nicht signierter Beitrag von 80.109.198.231 (Diskussion) 23:25, 10. Apr. 2013 (CEST))

Und muss es nicht "heapify(H, 0)" statt "heapify(H, i)" heißen (vorletzte Zeile)? -- 78.43.201.61 10:48, 6. Okt. 2013 (CEST)

decrease(H, i, lastIdx): Ist diese Zeile nicht falsch? Warum sollte der Parameter newkey von decrease() mit einem Index aufgerufen werden? (nicht signierter Beitrag von 2A02:908:FBD3:19C0:AD80:1E75:9B46:2EB4 (Diskussion) 16:54, 20. Jul. 2020 (CEST))

Vollständigkeit garantiert?

Mehrere Funktionen (remove, heapify und evtl. noch andere) funktionieren nur richtig, wenn der Heap vollständig ist. Dies wird jedoch in der Heap-Bedingung (und auch sonstwo) nicht gefordert.. Wie kann ich das verstehen? -- 78.43.201.61 10:55, 6. Okt. 2013 (CEST)

Anzahl der Kinder auf Level h

Im Abschnitt "Build" heißt es: ${\frac {n}{2^{h+1}}}$ (Aufrunden) gebe die Anzahl aller Kinder in der Höhe h an.

Wie kommt man auf diese Formel??

Nur mal als Beispiel:

     0
   /   \
  1     2
 / \  
3   4  (Index im Array, nicht Keys)

Dieser Heap hat die Höhe 2 und n = 5. Nach obiger Formel würde also gelten ${\frac {5}{2^{2+1}}}=7/8\approx 1{\text{ gerundet}}$ was falsch ist. Auf dem Level h+1 = 3 können max. 4 Teilbäume vorhanden bzw. auf Level 2 können die Knoten maximal 4 Kindsknoten besitzen. Allerdings wird ein Heap von links nach rechts aufgefüllt, d.h. haben die Knoten in diesem Beispiel eigentlich 0 Kinder. --94.134.251.62 22:20, 3. Okt. 2020 (CEST)