C/C++ Forum :: Binary Heaps

Zweimer Mitglied 19:52:54 12.05.2007 Titel:

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

Unregistrierter

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

Unregistrierter

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:

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

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

Code:
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:

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

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

Code:
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!

Unregistrierter

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?