Структуры данных и модели вычислений

         

Это действие может нарушить кучеобразный


Это действие может нарушить кучеобразный порядок лишь таким образом, что уменьшенный ключ элемента в узле станет меньше ключа элемента в родительском узле. Для восстановления порядка в куче используется операция ВСПЛЫТИЕ.

Вычислительная сложность данной операции определяется временем, затрачиваемым на уменьшение ключа (то есть константой), и временем выполнения операции ВСПЛЫТИЕ (то есть . В итоге вычислительная сложность операции УМЕНЬШИТЬ_КЛЮЧ равна .

Реализация операции УМЕНЬШЕНИЕ_КЛЮЧА

Операция ОКУЧИВАНИЕ.

Заметим, что если -куча создается путем -кратного применения операции ВСТАВКА, то суммарная трудоемкость ее создания будет равна . Если же все элементов сначала занимают в произвольном порядке массив и, соответственно, массив , то можно превратить их в -кучу, применяя операцию ПОГРУЖЕНИЕ по очереди к узлам .

Такой процесс будем называть окучиванием массива. Для доказательства того, что в результате действительно устанавливается кучеобразный порядок, достаточно заметить, что если поддеревья с корнями в узлах упорядочены по правилу кучи, то после применения процедуры ПОГРУЖЕНИЕ к узлу поддерево с корнем в этом узле также станет упорядоченным по правилу кучи. Итак, остановимся на следующей реализации.

Реализация операции ОКУЧИВАНИЕ

Утверждение 3.

Вычислительная сложность операции ОКУЧИВАНИЕ равна .

Доказательство

Заметим, что трудоемкость погружения с высоты

равна , а количество узлов высоты

не превосходит . Осталось оценить сумму где , и убедиться, что полученная сумма есть .

Для суммирования можно воспользоваться формулой

Предоставляем читателю возможность завершить доказательство.

Операция СОЗДАТЬ_СПИСОК_МИНИМАЛЬНЫХ.

Эта операция применяется для получения списка элементов, которые имеют ключи, меньшие заданного значения , и реализуется следующим образом. Если ключ элемента, находящегося в корне, больше, чем , то это дерево не имеет искомых элементов. В противном случае включаем его в выходной список , а затем применяем ту же процедуру ко всем потомкам узла, включенного в список.


Содержание  Назад  Вперед