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