VPF::Пирамидальная сортировка - Форум программистов

DimanNSK

Дата 26.5.2010, 14:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 20.3.2009

Репутация: нет
Всего: нет

У нас есть функция, осуществляющая пирамидальную сортировку:

Код


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, но в результате не отсортировываются два первых элемента.. Проясните ситуацию.. Пожалуйста.

toxx

Дата 26.5.2010, 14:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 4
Всего: 13

Цитата

потомки у звена дерева вычисляются как 2*k + 1 - левый и 2*k + 2 - правый

может они вычисляются 2*k-левый и 2*k+1-правый ?

DimanNSK

Дата 26.5.2010, 15:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 20.3.2009

Репутация: нет
Всего: нет

toxx, тогда для элемента с индексом 0, левый потомок будет иметь индекс 0, а правый 1.. Хотя по сути дела должны быть 1 и 2

toxx

Дата 26.5.2010, 17:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 653
Регистрация: 4.3.2009
Где: НН

Репутация: 4
Всего: 13

DimanNSK
а корень?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »