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