Структуры данных и модели вычислений



         

Вспомогательные структуры


Для представления толстой кучи введем новую структуру, которую назовем корневым счетчиком, а для того, чтобы быстро находить неправильные узлы, введем еще один избыточный счетчик, который назовем счетчиком нарушений. Таким образом, толстую кучу можно представить записью следующего вида:

где — массив, соответствующий корневому счетчику; — массив, соответствующий счетчику нарушений; — указатель на элемент кучи, имеющий минимальный ключ; — наибольший ранг среди рангов деревьев, присутствующих в куче.

Корневой счетчик. Корневой счетчик состоит из избыточного троичного представления числа элементов в куче и набора списочных элементов.

Значение -го разряда избыточного корневого представления равно количеству деревьев ранга , присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга содержит ровно узлов. Заметим, что состояние избыточного корневого представления определяется неоднозначно. Отсюда следует, что толстая куча с одним и тем же набором элементов может быть представлена различными наборами толстых деревьев. Очевидно, что для любой толстой кучи, состоящей из элементов, существует регулярное избыточное представление корневого счетчика.

Списочный элемент, приписанный -му разряду избыточного корневого представления, — это указатель на список деревьев ранга , присутствующих в куче, образованный посредством указателей корневых узлов связываемых деревьев.

Определение корневого счетчика дает возможность сделать несколько утверждений:

  1. Корневой счетчик позволяет иметь доступ к корню любого дерева ранга за время .
  2. Вставка толстого дерева ранга соответствует операции инкрементирования -го разряда корневого счетчика.
  3. Удаление толстого поддерева ранга соответствует операции декрементирования -го разряда корневого счетчика.
  4. Операции инкрементирования и декрементирования -го разряда корневого счетчика осуществляются за время .

Представление корневого счетчика. Корневой счетчик представляем расширяющимся массивом , каждый элемент которого — запись с тремя полями:


Содержание  Назад  Вперед