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