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