kann geschlossen werden, hab's selbst gelöst - danke für die Nicht-Hilfe
-
Hallo,
ich hänge irgendwie seit Tagen an einem Problem und sehe irgendwie den Wald vor lauter Bäumen nicht mehr.
Folgendes: Ich möchte eine Bubbledown-Funktion für ein d-näres Heap implementieren (also statt 2 gibt es d Kinder). Dabei ist A mein Array des Heaps (linksvollständiger Baum, Levelorder), N die Knotenanzahl, p der Knoten, an den es eine fehlstellung gibt und D dementsprechend die maximale Kinderanzahl pro Knoten (ich gehe erstmal von 2 bis 16 - wird per Zufall gezogen).
Ich hatte mir überlegt, das zunächst das erste Kind von p zu bestimmen ist (=leftchild) und ich die Kinder dann abzähle, um die maximale Anzahl aller zu berechnen (=rightchild). je nachdem, ob ich im oder nicht im letzten Level bin, durchlaufe ich verschiedene Wege. Bin ich nicht im letzten Level, dann suche ich das kInd mit dem kleinsten Schlüssel, vergleiche es mit p und tausche falls notwendig. Habe ich getauscht, dann setze ich p neu, berechne neue das erste Kind und zähle nochmals alle Kinder durch. Bin ich irgendwann im letzten Level, so verlasse ich die Hauptschleife und suche nur noch das Kind mit dem kleinsten Schlüssel, und tausche es bei Bedarf mit p.
Ich weiß nicht, ob ich irgendwo einen Denkfehler habe, aber irgendwie klemmt's...
Was ich mir denke: Ich brauche gar nicht die Kinder durchzählen, sondern vergleiche gleich mit D, das ich ja habe - aber wo ist noch ein Fehler?!inline void BubbleDown( T A[], const uint N, uint p, const uint D ) { typedef typename T::key_type K; ///////////////Festelgen der Kinderindices////////////////////////////////////// int leftchild = D*p + 1; //erstes Kind von p int minchild = leftchild; //Kind mit MIN-Schlüssel int rightchild = leftchild; //maximale Anzahl der Kinderknoten //Ermitteln des Elternindexes // int parent = (p-1)/D; bool done = false; //Hilfvariable der Hauptschleife bool weiter = false; //Hilfsvariable für erneutes auszählender Kinderknoten //////////////////////////////////////////////////////////////////////////////// ////////ermitteln der Anzahl der Kinderknoten/////////// if(leftchild < (N-1)){ while (rightchild < (D*p + D) && rightchild < (N-1)) { ++rightchild; } } else{ return; // ab hier keine Vergelcihe mehr, da nur noch Elternknoten da } ///////////////////////Hauptschleife////////////////// while (!done && rightchild == leftchild + (D-1)) { ///////ermitteln des Kindknoten mit kleinstem Schlüssel while(rightchild != leftchild){ //suchen des kleinsten Kindes --> speichern in minchild if(A[rightchild].Key()< A[minchild].Key()){ minchild = rightchild; --rightchild; } else { --rightchild; } } //////Ist minchild kleiner parent?/////// if (A[minchild].Key() < A[p].Key()) { A[N] = A[p]; A[p] = A[minchild]; A[minchild] = A[N]; } else { done = true; weiter = true; // return; } // ab hier nichts mehr tun, da bereits Heap /////falls Elternknoten getauscht wurde, dann ermittele neue Kinderknoten///////// if (!weiter) { p = minchild; leftchild = D*p + 1; rightchild = leftchild; minchild = leftchild; ////////neues Auszählen der Kinder///////// if (leftchild < (N-1)) { while(rightchild < (D*p + D) && rightchild < (N-1)){ ++rightchild; } } else { done = true; //parent hat keine Kinderknoten mehr, Ende Hauptschleife } ///////wenn nicht genau D Kinder, dann beende die while-Schleife if (rightchild != (leftchild + (D-1))) { done = true; // rightchildprim = leftchild; // rightchild = rightchildprim; } else{ done = false; } } } /////////////////////////////////////// letztes Level ////////////////////////// //ermitteln des MIN der Kinder // if (leftchild < N-1) { // && leftchild != (N+1)) { /* while(rightchild < (D*p + D) && rightchild < (N-1)){ ++rightchild; } */ while (rightchild != leftchild) { if (A[rightchild].Key() < A[minchild].Key()) { minchild = rightchild; --rightchild; } else{ --rightchild; } } //prüfen, ob mit Elternknoten getaucht werden muss if (A[minchild].Key() < A[p].Key()) { A[N]= A[p]; A[p] = A[minchild]; A[minchild]= A[N]; } else{ return; } }
-
Es klemmt - aha.
-
ja^^
-
erbsemöhre schrieb:
ja^^
manni66 wollte mit seinem Beitrag sicherlich nicht nur aussagen, dass er deinen Beitrag zur Kenntnis genommen hat. Denk mal darüber nach, warum er wohl
manni66 schrieb:
Es klemmt - aha.
geschrieben haben könnte.
-
wahrscheinlich wegen eines offensichtlichen Fehlers, den ich nicht sehe...
-
Du gehst wohl auch zum Arzt und sagst nur "Ich bin krank".
-
Du gehst wohl auch zum Arzt und sagst nur "Ich bin krank".
Ja, ich habe Patienten, die sich so vorstellen - meine Aufgabe ist es dann, nach Lokalisation und Ursachen zu fragen - nennt sich allgemein bekannt "eine Anamnese erheben"
Nun gut: Fällt jemanden vielleicht auf den ersten Blick etwas auf, das kompletter Humbug ist, und folglich eine Ursache des Fehlers sein könnte? Mit den Tauschaktionen: Ich war mir da nicht ganz sicher: Sollte ich die Keys tauschen oder stimmt das so mit den Array-Einträgen? Ist es zu umständlich die Kinderknoten zu zählen oder sollte ich das irgendwie umgestalten, damit es sinnvoller wird. (und nicht, dass ich das schon im Eingangspost gefragt hätte...) - kann es sein, dass meine Grundidee schon einem Denkfehler aufsitzt?
Ich wäre sehr um konstruktive Antworten dankbar.
-
okay, ich habe es nochmals umgeschrieben
int leftchild = D*p +1; int minchild = leftchild; int rightchild = leftchild + (D-1); while (rightchild < (N-1)) { for (int i = rightchild; i != leftchild; i--) { if (A[i].Key() < A[minchild].Key()) { minchild = i; } } if (A[p].Key() <= A[minchild].Key()) { return; } else { swap(A[minchild], A[p]); p = minchild; leftchild = D*p +1; minchild = leftchild; rightchild = leftchild + (D-1); } } if (leftchild <= (N-1)) { rightchild = leftchild; } while (rightchild < (leftchild + (D-1))) { rightchild++; } for (int j = rightchild; j != leftchild; j--) { if (A[j].Key() < A[minchild].Key()) { minchild = j; } } if (A[minchild].Key() < A[p].Key()) { swap(A[minchild], A[p]); }meine Frage: ich müsste doch wissen, ob p genau d kinder hat - wie kann ich das aufschreiben, wenn ich z.B. nur leftchild habe?
-
und noch eine frage: Wie kann ich auf dem letzten Level die Kinderanzahl ermitteln? Ich mache das in den Zeilen 27-33 - kann ich das so machen?
-
es ist schwer, zu verstehen, was deine frage ist (was funktioniert nicht?), auch, weil - vor allem im ersten beispiel - die vielen kommentare, leerzeichen und (auf den ersten blick falsch wirkenden) einrückungen das verfolgen des codes (was willst du eigentlich tun vs. wie ist es implementiert) extrem schwer machen. in deinem zweiten beispiel wirken einige konstrukte irgendwie merkwürdig. einer der gründe dafür ist, dass dein code nicht wirklich ausdrückt, was er tut (man muss erst sozusagen viele zeiger im kopf behalten) und im ersten beispiel die kommentare auch nicht wirklich helfen.
ein beispiel:for (int i = rightchild; i != leftchild; i--) { if (A[i].Key() < A[minchild].Key()) { minchild = i; } }bringt es dir hier einen vorteil, von hinten durchzuzählen? vielleicht habe ich das überlesen. jedenfalls wäre viel ausdrucksstärker, diese schleife in einer solchen form zu formulieren:
minchild = distance(A, min_element (A+leftchild, A+rightchild, [] (const A& a, const A& b) { return a.Key() < b.Key(); });weil dann gleich klar ist, was in der variable minchild gespeichert ist. und vielleicht kann man dann auch noch sagen wegoptimieren (isv den code kürzer/lesbarer machen), z.b.
distance. (plus tipp D, p, A und N könnte man auch bessere namen geben, sonst muss man immer zwischen text und code herumspringen - macht es auch nicht grade lesbarer)dieser code wirkt auch sehr seltsam:
if (leftchild <= (N-1)) { rightchild = leftchild; }N ist die länge des arrays A? dann sollte die bedingung ja wohl hoffentlich immer true sein. oder anders gesagt, du brauchst sie nicht.
while (rightchild < (leftchild + (D-1))) { rightchild++; }wozu eine schleife?
vielleicht brauchst du so etwas wie
//rightchild ist plötzlich: anzahl der knoten auf dem letzten level (?) rightchild = min (N-leftchild, D);
-
danke für deine Antworten!
dove schrieb:
C++: minchild = distance(A, min_element (A+leftchild, A+rightchild, [] (const A& a, const A& b) { return a.Key() < b.Key(); });wahrscheinlich wäre es eleganter es so schreiben - aber wenn ich ehrlich bin, kann ich damit (noch) nicht viel anfangen. Ich nutze die Schleife, um das kleinste Element; zu suchen - ich denke, dass es seinen Zweck erfüllt (Einsprüche bitte immer her!), auch wenn es vielleicht nicht der schönste Code ist.
dove schrieb:
dieser code wirkt auch sehr seltsam:
C++: if (leftchild <= (N-1)) { rightchild = leftchild; }ich möchte damit prüfen, ob p überhaupt noch ein Kind hat - wenn nicht, dann bin ich ja fertig. Deshalb diese komisches Konstrukt. Errechne ich ein theoretisches Leftchild von z.B. 19, habe aber nur 17 Knoten, dann (meine ich) damit zu wissen, dass es gar keine Kinder mehr für den Knoten geben kann.
dove schrieb:
dieser code wirkt auch sehr seltsam:
C++: //rightchild ist plötzlich: anzahl der knoten auf dem letzten level (?) rightchild = min (N-leftchild, D);das bringt mir nicht viel, da ich nicht wissen muss, wieviel Kinder auf dem letzten Level sind, sondern wieviel Kinder ein Knoten (und zwar, der den ich gerade anschaue) des letzten Levels hat, deren Anzahl nicht D ist (also ein Knoten mit mindestens 0 und höchstens D-1 Knoten) - die Info reicht mir ja, um nur noch das Minimum zu suchen und ggf. mit p letztmalig zu tauschen.
-
hat keiner eine Antwort für mich?
-
int leftchild = D*p +1; int minchild = leftchild; bool done = false; int countkids; while (!done && (D*p + D) <= (N-1)) { for (int i = leftchild+1; i <= (D*p+ D); i++) { if (A[i].Key() < A[minchild].Key()) { minchild = i; } } if (A[p].Key() <= A[minchild].Key()) { done = true; } else { swap(A[minchild], A[p]); p = minchild; leftchild = D*p +1; minchild = leftchild; } } leftchild = D*p+1; if ( !done ){ //leftchild < (N)) { // if (leftchild <= (N-1)) { if (leftchild > N - 1) { return; } countkids = leftchild +(N-1-leftchild); for (int j = leftchild + 1 ; j <= countkids; j++) { if (A[j].Key() < A[minchild].Key()) { minchild = j; } } if (A[minchild].Key() < A[p].Key()) { swap(A[minchild], A[p]); } else return; } else return;also, der funktioniert, liefert aber eine falsche Reihenfolge in der Ausgabe- Sieht wer, woran das liegen könnte?
