Эта глава посвящена «кучам» — структурам данных, используемых для решения двух важных задач.
1. Сортировка. Сортировка массива размера п с помощью кучи выполняется за время, ни при каких условиях не превышающее O(nlogn). Кроме того, этот метод сортировки использует лишь несколько байт дополнительной памяти.
2. Очереди с приоритетом. Для куч поддерживаются операции добавления нового и удаления наименьшего элемента. Каждая из этих операций выполняется за время <9(log п).
В обеих задачах кучи облегчают программирование и сокращают объем вычислений.
Эта глава организована по принципу «снизу вверх»: мы начнем с подробностей и только потом перейдем к решению задач. В двух первых разделах главы описывается структура кучи и две функции, к ней применяемые. В двух следующих разделах мы покажем, как пользоваться кучами и упомянутыми функциями для решения описанных выше задач.
Главная
Каталог файлов
