Binary Heaps

Maxi

Sehr guter Artikel!

Wieder was gelernt Ich dacht immer so Heaps sind viel schwerer. Na dann wohl doch nicht

Noch einen rechtschreibfehler in der STL-Sektion:

Erwartet, dass [big, end) ein Heap ist und nimmt das größte Element aus dem Heap heraus und legt es an der nun frei werdenden Stelle end-1 ab.

big -> beg

Und nochwas:
Wäre es nicht besser, Pointer auf die Objekte zu speichern? Dann fallen die ganzen Kopierkonstruktionen aus, die bei größeren Objekten anfallen könnten. Allerdings müsste man dann gucken, dass die Daten auf dem heap liegen. Oder man kopiert zu speichernde Daten in ein array und die daten auf dem heap sind pointer auf die elemente des arrays

Jester

Danke für das Lob.

Kurz zu den Anmerkungen:

KasF: Ne, einfach nicht drauf geachtet. Aber letztlich ist es vielleicht eh besser nen std::vector reinzubaun und den einfach auf der richtigen Größe zu halten. Das hätte aber den Code tatsächlich komplizierter (wenn auch nur ganz wenig) gemacht. Daher ist es nicht drin.

ruediger: Wenn Du alles genau gelesen hättest wüßtest Du, dass die Antwort const sein muß. Schließlich soll in compare dann ja mal ein Komparator verwendet werden, und das paßt nicht zu static.

Und damit auch der Übergang zur letzten Anmerkung.
Maxi: Ich denke die Implementierung ist so schon in Ordnung. Das was Du willst geht ja trotzdem. Sobald Du die Variante mit dem Komparator gebaut hast kannst Du einfach einen Heap<MyObject*> anlegen und einen geeigneten Komparator zum Vergleichen der Pointer übergeben.

elise

thanks, Jester

warum sind bei der deleteMin alternative die 4 und 6 vertauscht? die waren doch vorher richtigrum

Jester

frage schrieb:

warum sind bei der deleteMin alternative die 4 und 6 vertauscht? die waren doch vorher richtigrum

Da ist mir wohl in der Zeichnung ein Fehler unterlaufen. Ich schau mal, dass ich das demnächst noch korrigieren. Danke für den Hinweis!

Ben04

Der Abschnitt über die Theorie ist sehr gelungen. Besonders die Graphiken tragen viel zum Verständnis bei. Der Text ist auch gut und fließend lesbar. Kurz, klar und doch ist alles drin.

Die Implementierung ist auch nicht schlecht allerdings gefallen mir da manche Sachen nicht so sehr. Die ganzen getFather Methoden hätte ich als frei inline Funktionen implementiert. Auf diese Weise hat man nicht eine Kopie für jeden T und jede Größe und es wird kein nicht gebrauchter this Pointer übergeben. Jeder Optimizer sollte hier zwar aufräumen können jedoch gibt das sehr viele unnütze zusätzliche Symbole die auf die Geschwindigkeit des Debugger und Linkers schlagen können.

Welches Programm hast du für die Graphiken verwendet?

Jester

Ben04 schrieb:

Die ganzen getFather Methoden hätte ich als frei inline Funktionen implementiert.

Könnte man machen. Andererseits werden die eh geinlined und sinn dann weg. Die sind ja eh nur der besseren Lesbarkeit wegen da. Insofern finde ich's vertretbar.

Welches Programm hast du für die Graphiken verwendet?

Die Grafiken habe ich mit ipe erstellt. http://tclab.kaist.ac.kr/ipe/
Ist aber auch bei vielen Linux-Distributionen dabei.

Zweimer

Jester, dein Artikel ist sehr gelungen. Großes Lob an dich.

Guter Artikel!

Eine Erklärung zum Pairing Heap wär auch Interessant
Hab irgendwie noch nirgends gefunden wie der Pairing Heap nun wirklich funktioniert.

mfg lavandyke

Ein guter Artikel, der die Funktionsweise von Heaps gut mit den templatisiert vorgestellten Funktionen darstellt. Es wird deutlich, wie das Interface eines Heaps realisiert werden kann.
M.E. haben sich im vorgestellten Beispielcode an 2 Stellen kleine Fehler eingeschlichen:
Zeile 13 in getMin:

child += (!isLastElement(child) && compare(elements_[child+1], elements_[child]));

Ist hier nicht ein ternärer Bedingungsoperator als Voraussetzung für die Addition vorgesehen, also ein ? wahr:falsch-Konstrukt ?

Im letzten Codebeispiel vor dem Ausblick heißt es in Zeile 1:

int data[10] = {11,5,14,12,3,4,9, 8, 20};

Das Array data enthält nur 9 Elemente, die 20 wird also gleich mit berücksichtigt und nicht erst später, wie im Quelltext angenommen.

Vielen Dank für den schönen Artikel!

Inwiefern unterscheidet sich diese Implementierung von der klassischen? Ich kenne nur diese und diese wird in Cormen - Introduction to Algorithms auch vorgestellt.

Wäre die klassische eine tatsächliche Implementierung als Baum?