Эта глава посвящена «кучам» — структурам данных, используемых для решения двух важных задач.
1. Сортировка. Сортировка массива размера п с помощью кучи выполняется за время, ни при каких условиях не превышающее O(nlogn). Кроме того, этот метод сортировки использует лишь несколько байт дополнительной памяти.
2. Очереди с приоритетом. Для куч поддерживаются операции добавления нового и удаления наименьшего элемента. Каждая из этих операций выполняется за время <9(log п).
В обеих задачах кучи облегчают программирование и сокращают объем вычислений.
Эта глава организована по принципу «снизу вверх»: мы начнем с подробностей и только потом перейдем к решению задач. В двух первых разделах главы описывается структура кучи и две функции, к ней применяемые. В двух следующих разделах мы покажем, как пользоваться кучами и упомянутыми функциями для решения описанных выше задач.
Опубликовал vovan666
April 17 2013 00:03:59 ·
0 Комментариев ·
2413 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
