Структуры данных и модели вычислений
Процедура удаления дерева из кучиподразумевает
Трудоемкость этой операции равна .
Процедура удаления дерева из кучиподразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг . Тогда значение -го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть. Процедура реализуется операторами
Трудоемкость операции .
Нахождение дерева с минимальным ключом в корне реализуется операторами
Трудоемкость данной операции также .
Счетчик нарушений. К сожалению, здесь не удается разделить работу с избыточным представлением и списочной частью, как в корневом счетчике. Поэтому рассмотрим работу со счетчиком нарушений более подробно. Счетчик нарушений состоит из расширенного избыточного двоичного представления и набора списочных элементов.
Отличие заключается в том, что:
- Нас теперь интересует не само число, а только значения разрядов.
- Операция фиксации тесно связана с толстой кучей.
Значение -го разряда для счетчика нарушений интерпретируется как количество неправильных узлов ранга , а его списочная часть — это указатели на неправильные узлы ранга .
Такое определение счетчика нарушений дает возможность сделать несколько утверждений:
- Наличие счетчика нарушений позволяет иметь доступ к любому неправильному узлу ранга за время .
- Уменьшение ключа у элемента ранга
соответствует операции инкрементирования -го разряда счетчика нарушений (естественно, лишь в случае, когда новое значение ключа у изменяемого узла становится меньше значения ключа его родителя). - Операции инкрементирования и декрементирования -го разряда осуществляются за время .
Представление счетчика нарушений. Счетчик нарушений — это расширяющийся массив, элементы которого являются записями из четырех полей
со следующей интерпретацией:
— количество неправильных узлов ранга в куче, — прямой указатель -го разряда,
и — указатели на неправильные узлы ранга .
Заметим, что если значение
равно единице, то важно лишь значение первого указателя и не играет роли значение второго . Если равно нулю, то неинтересны оба указателя.
Далее ограничимся рассмотрением только наиболее важных операций. Так как счетчик нарушений похож на описанный выше корневой счетчик, акцентируем внимание лишь на различиях. Реализация всех необходимых процедур остается читателю в качестве упражнения.
Инициализация нового звена. Для инициализации нового звена счетчика нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга . Это первый момент появления в куче узла ранга . Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного , соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
