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