Структуры данных и модели вычислений
Это действие может нарушить кучеобразный
Это действие может нарушить кучеобразный порядок лишь таким образом, что уменьшенный ключ элемента в узле станет меньше ключа элемента в родительском узле. Для восстановления порядка в куче используется операция ВСПЛЫТИЕ.
Вычислительная сложность данной операции определяется временем, затрачиваемым на уменьшение ключа (то есть константой), и временем выполнения операции ВСПЛЫТИЕ (то есть . В итоге вычислительная сложность операции УМЕНЬШИТЬ_КЛЮЧ равна .
Реализация операции УМЕНЬШЕНИЕ_КЛЮЧА
Операция ОКУЧИВАНИЕ.
Заметим, что если -куча создается путем -кратного применения операции ВСТАВКА, то суммарная трудоемкость ее создания будет равна . Если же все элементов сначала занимают в произвольном порядке массив и, соответственно, массив , то можно превратить их в -кучу, применяя операцию ПОГРУЖЕНИЕ по очереди к узлам .
Такой процесс будем называть окучиванием массива. Для доказательства того, что в результате действительно устанавливается кучеобразный порядок, достаточно заметить, что если поддеревья с корнями в узлах упорядочены по правилу кучи, то после применения процедуры ПОГРУЖЕНИЕ к узлу поддерево с корнем в этом узле также станет упорядоченным по правилу кучи. Итак, остановимся на следующей реализации.
Реализация операции ОКУЧИВАНИЕ
Утверждение 3.
Вычислительная сложность операции ОКУЧИВАНИЕ равна .
Доказательство
Заметим, что трудоемкость погружения с высоты
равна , а количество узлов высоты
не превосходит . Осталось оценить сумму где , и убедиться, что полученная сумма есть .
Для суммирования можно воспользоваться формулой
Предоставляем читателю возможность завершить доказательство.
Операция СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ.
Эта операция применяется для получения списка элементов, которые имеют ключи, меньшие заданного значения , и реализуется следующим образом. Если ключ элемента, находящегося в корне, больше, чем , то это дерево не имеет искомых элементов. В противном случае включаем его в выходной список , а затем применяем ту же процедуру ко всем потомкам узла, включенного в список.
