downHeap, upHeap..Unterschied?

julchatt

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)
    }
}

314159265358979

Der Code ist sowohl richtig kotz-hässlich, als auch kein gültiges C++. Welcher Compiler übersetzt sowas?

julchatt

sag das meinem Prof)))...ist es den ein downHeap oder upHeap????

Shade Of Mine

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.

julchatt

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

Shade Of Mine

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?