downHeap, upHeap..Unterschied?
-
Hallo Leute, ich habe hier vom Professor implementierte DownHeap Methode, die ziemlich nach upHeap aussieht, weil es die Kinder mit dem Vater verglichen werden...bitte um Hilfe und einen Ratschlag, weil wir ein upHeap schreiben müssen und wissen einfach nicht weiter...
void PriorityQueue::DownHeap(int i, int n, int a[n]){ int i,largest,n; // i ist der Vater int l = 2*i; //leftChildIndex, Nachfolger des Vaterknotens int r = 2*i+1; //rightChildIndex, Nachfolger des Vaterknotens if( l <= n && (a[l] > a[i]) ) { largest = l; } else { int largest = i; } if( int r <= n && (a[r] > a[largest]) ) { largest = r; } if( largest != i ) { vertausche(a[i], a[largest]) DownHeap(largest, n, a) } }
-
Der Code ist sowohl richtig kotz-hässlich, als auch kein gültiges C++. Welcher Compiler übersetzt sowas?
-
sag das meinem Prof)))...ist es den ein downHeap oder upHeap????
-
Ne das passt schon, das ist down-heap. Sofern da nicht irgendwo ein Fehler drinnen steckt - aber von der Idee her passt es schon.
Auf wikipedia wird das mit folgendem Satz IMHO schoen beschrieben:
http://en.wikipedia.org/wiki/Heapsort schrieb:
This "siftUp" version can be visualized as starting with an empty heap and successively inserting elements, whereas the "siftDown" version given above treats the entire input array as a full, "broken" heap and "repairs" it starting from the last non-trivial sub-heap (that is, the last parent node).
@314159265358979:
Dein Beitrag ist komplett Sinnlos. Bitte versuche konstruktive Beitraege zu schreiben.
-
tut mir Leid, aber ich verstehe es trotzdem nicht, bzw. die Erklärung gibt mir leider kein Aufschluss darüber wo jetzt der Unterschied bezogen auf den gezeigten COde zwische upHeap und downHeap ist...
???????????????????? (((
HILFE!!!
-
julchatt schrieb:
tut mir Leid, aber ich verstehe es trotzdem nicht, bzw. die Erklärung gibt mir leider kein Aufschluss darüber wo jetzt der Unterschied bezogen auf den gezeigten COde zwische upHeap und downHeap ist...
Auf dem verlinkten Wikipedia Artikel sind beide Variante implementiert. Sie sehen sich nicht wirklich ähnlich. Was genau ist deine Frage?