Алгоритм сортировки с помощью кучи работает в два этапа. На первых п шагах массив переводится в кучу, а на следующих п шагах элементы извлекаются из кучи в порядке убывания и образуют упорядоченную последовательность элементов, увеличивающихся слева направо.
Итак, на первом этапе формируется куча. На протяжении этого процесса инвариант может быть изображен следующим образом (рис. 14.9).
куча ?
1 /' п
Рис. 14.9. Инвариант на первом этапе
Программа в листинге 14.8 делает истинным высказывание heap(l, п), просеивая элементы к началу массива.
Листинг 14.8. Первый этап сортировки heapsort: формирование кучи
for ^ = [2, п]
/* инвариант- hеар(1. п-1) */
S 1 ftup( )
/* heaрС1. i) */
На втором этапе куча используется для формирования упорядоченной последовательности. Инвариант этого этапа изображен на рис. 14.10.
куча, ?
отсортировано,?
1 / п
Опубликовал vovan666
April 17 2013 00:04:24 ·
0 Комментариев ·
7013 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
