7. Модифицированный двоичный попек начинается с элемента i = 1 и на каждой итерации присваивает переменной i значение 2*i либо 2*i+1. В элементе х[ 1 ] содержится медиана, в х[2] — первая квартиль, в х[3] — третья квартиль и так далее. С. Р. Махани (S. R. Mahaney) и Дж. И. Мунро (J. I. Munro) нашли алгоритм упорядочения п-элементного предварительного отсортированного массива в порядке «heapsearch» за время О(п) и с применением постоянной дополнительной памяти.
Чтобы дойти до их метода, попробуйте скопировать отсортированный массив а размера 2k_1 в массив Ь, предназначенный для поиска: элементы, стоящие на четных позициях, в а помещаются во вторую половину массива, Элементы, стоящие на позициях 2 mod 4 , — во вторую четверть массива Ь, и так далее.
11. Стандартная библиотека шаблонов C++ STL поддерживает кучи и операции для них: make_heap; push_heap, pop_heap, sort„heap. Из них легко получит!) сортировку heapsort:
так e hеа р(а, а + л) . sort_heaр(а . а+п) .
В библиотеке STL имеется также адаптер priority_queuе.
Опубликовал vovan666
April 17 2013 00:07:14 ·
0 Комментариев ·
3432 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
