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