vendredi 2 septembre 2016

Problems with BubbleSort in a d ary heap in C++

i have a data structure for a bubbleDown - function of a d-ary heap. It should be really simple, but there must be a mistake, that i can't see...

so, p ist the parent, which destroy the heap, D is the number of the children, and N is the complete number of all nodes. And A ist the Array, that contains all. I thought, i find the children with the smallest key and swap it with p. If p doesn't have all D children, i just searching that one children with the smallest key and swap it with p. Can anybody help me and give some advice to improve the code?! Please be kind, i'm a newbie in coding..

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

    if ( !done ){ //leftchild < (N)) {
        if (leftchild <= (N-1)) {
              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;
    }

    else return;

Aucun commentaire:

Enregistrer un commentaire