Используя функции из решеиий задач 1 и 2, сортировку heapsort можно записать следующим образом
3. Используя функции из решеиий задач 1 и 2, сортировку heapsort можно записать следующим образом:
for (i = п/2 - i >= 1: 1 -') s1ftdown1(i. n) for (i = n: i >= 2 : i - -) swap(1, i ) siftdown(1, i-1)
Время выполнения остается равным 0(п log п), по константа оказывается меньшей, чем для исходной версии сортировки с помощью кучи. В моей программе, сравнивающей различные сортировки, приводится несколько реализаций алгоритма heapsort. Программу можно скачать с сайта книги.
4. Кучи позволяют перейти от алгоритма О(п) к (3(log/?) в перечисленных ниже задачах:
а) на каждом шаге итеративного построения кода Хаффмана выбираются два минимальных элемента в наборе, после чего они сливаются в новый узел.
Это реализуется двумя вызовами extractmin и одним insert. Если входные частоты представить в порядке возрастания, то код Хаффмана может работать с линейной скоростью. Подробности реализации оставляются читателю в качестве упражнения;
б) простой алгоритм суммирования вещественных чисел может оказаться недостаточно точным, если складывать очень большие числа с очень маленькими. Болес совершенный алгоритм всегда должен складывать два наименьших элемента набора, п вообще он изоморфен упомянутому выше алгоритму нахождения кодов Хаффмана;
в) куча с миллионом элементов (наименьший находится на вершине кучи) представляет миллион наибольших на данный момент чисел;
г) куча может использоваться для слияния отсортированных файлов. На каждом шаге итеративного алгоритма наименьший элемент извлекается из кучи, а следующий за ним помещается в кучу. Очередной элемент, выводимый из п файлов, может быть найден за время 0(log л).
5. Структура, аналогичная куче, может быть создана поверх последовательности корзин. Каждый узел кучи храпит информацию о самой свободной корзине среди его дочерних. Когда делается выбор, куда класть груз, поиск сначала идет влево, если есть возможность (самая свободная корзина слева имеет достаточно места для груза), либо вправо, если это необходимо. Эта операция выполняется за время, пропорциональное высоте кучи, то есть 0(log /7). После размещения груза значения элементов кучи должны быть реорганизованы обратным ходом.
Опубликовал vovan666
April 17 2013 00:07:10 ·
0 Комментариев ·
3940 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
