У нас есть функция, осуществляющая пирамидальную сортировку:
| Код |
void sortByHeap(table* t)
{
int i;
elemTable temp;
for (i = t->size / 2; i >= 0; i--)
downHeap(t, i, t->size - 1);
for(i = t->size - 1; i > 0; i--)
{
temp = t->data[i];
t->data[i] = t->data[0];
t->data[0] = temp;
downHeap(t, 0, i - 1);
}
}
void downHeap(table* t, int k, int n)
{
elemTable new_elem;
int child;
new_elem = t->data[k];
while(k <= n / 2)
{
child = 2 * k;
if ((child < n) && (t->data[child].num < t->data[child + 1].num))
child++;
if (new_elem.num >= t->data[child].num)
break;
t->data[k] = t->data[child];
k = child;
}
t->data[k] = new_elem;
}
|
Сортирует все правильно, я одного понять не могу, почему мы child делаем равным 2*k, ведь потомки у звена дерева вычисляются как 2*k + 1 - левый и 2*k + 2 - правый. Я попробовал child = 2*k + 1, но в результате не отсортировываются два первых элемента.. Проясните ситуацию.. Пожалуйста. |