000
13.08.2014, 22:44 Uhr
MissMarshall
|
Guten Abend,
ich soll ein d-näres Heap programmieren und stecke nun seit fast eine Woche mit dem Code fest. Problem ist die BubbleDown-Funktion.
Bin gerade im 2. Semester Informatik und hatte zuvor noch nie programmiert. Selbst zu Schulzeiten nicht. Bin also blutige Anfängerin. Der Code ist nicht gerade optimal oder sehr 'schön'. Und leider auch nicht wirklich funktionsfähig. Nun will ich das Ding aber zum Laufen bringen und wäre wirklich um jede kleinste Hilfestellung dankbar!
| C++: |
inline void BubbleDown( T A[], const uint N, uint p, const uint D )
{
typedef typename T::key_type K;
/// TODO Anfang
int k = 1;
int child = (p * D) + k;
int minChild = child;
int maybeChild;
int count = 0;
bool done = false;
while(!done && (p <= ((N-2)/D)))
{
for(int i=1; i<=D; ++i) // Kinder zählen <-- wahrscheinlich klappt so nicht...
{
child = (p * D) + i;
count ++;
}
if(count = D) // 1. Fall: p hat genau D Kinder
{
for(k = 2; k <= D; ++k) // Index des kleinsten Kindes finden
{
maybeChild = child;
if(A[maybeChild].Key() < A[minChild].Key())
{
minChild = maybeChild;
}
}
if(A[p].Key() <= A[minChild].Key()) // Probe, ob wirklich kleiner als p
done = true;
else // falls ja: Tausche beide
{
swap(A[p], A[minChild]);
p = minChild; // p ist nun eine Ebene tiefer
}
}
if(count < D)
{
maybeChild = count;
while(maybeChild > 1)
{
if(A[maybeChild].Key() < A[minChild].Key())
{
minChild = maybeChild;
}
--maybeChild;
}
if(A[p].Key() <= A[minChild].Key())
done = true;
else
{
swap(A[p], A[minChild]);
done = }false;
}
}
/// TODO Ende
}
|
|
