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