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

         

у узла нет потомков, то


Если у узла нет потомков, то .

Реализация операции ПОГРУЖЕНИЕ

Операция ВСТАВКА. Если перед выполнением этой операции куча содержала узлов (напомним, что они пронумерованы числами от

до ), то добавляем к дереву -й узел (его номер будет ) и приписываем ему элемент с именем и ключом . Вставка нового элемента производится посредством отведения для него места в -ых позициях массивов и соответственно, после чего к добавленному узлу применяется операция ВСПЛЫТИЕ для восстановления кучеобразного порядка.

Вставим в -кучу, изображенную на рис. 4.9, новый элемент с ключом .

Рис. 4.9. 

Сначала добавляем к дереву новый узел с номером и приписываем ему элемент с ключом . Получим дерево, представленное на рис. 4.10.

Рис. 4.10. 

Затем применяем к узлу операцию ВСПЛЫТИЕ. При описании этой операции использовался именно приведенный пример (см. рис. 4.3, 4.4, 4.5).

Вычислительная сложность данной операции равна константе плюс вычислительная сложность операции ВСПЛЫТИЕ, то есть .

Реализация операции ВСТАВКА

Операция УДАЛЕНИЕ.

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

Таким образом, ориентируясь на худший случай, вычислительную сложность операции УДАЛЕНИЕ оцениваем величиной .

Реализация операции УДАЛЕНИЕ

Операция УДАЛЕНИЕ_МИНИМУМА. Эта операция предназначена для взятия из кучи элемента с минимальным ключом (он находится в корне дерева) и удаления его из кучи с помощью операции УДАЛЕНИЕ.

Реализация операции УДАЛЕНИЕ_МИНИМУМА

Функция MINKEY. Эта функция предназначена для определения минимального ключа без удаления соответствующего элемента.

Реализация функции MINKEY

Трудоемкость операции, очевидно, равна .

Операция УМЕНЬШЕНИЕ_КЛЮЧА. Предназначена для уменьшения ключа у элемента, приписанного узлу с заданным номером , на заданную величину .

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