497
правок
Изменения
→Вспомогательные структуры
=Вспомогательные структуры=
Нам понадобятся понятия '''корневого счетчика''' и '''счетчика нарушений'''.
Толстую кучу будем представлять записью следующего вида:
<tex>FatHeap = (RootCount, CountViolation, Minpointer, MaxRank)</tex>, где:
<tex>RootCount</tex> {{---}} массив, соответствующий корневому счетчику
<tex>CountViolation</tex> {{---}} массив, соответствующий счетчику нарушений
<tex>MinPointer</tex> {{---}} указатель на элемент кучи с минимальным ключом
<tex>MaxRank</tex> {{---}} наибольший ранг среди рангов деревьев, присутствующих в куче
==Корневой счетчик==
'''Корневой счетчик''' состоит из избыточного троичного представления числа элементов в куче и набора списочных элементов.
Значение его <tex>i</tex>-го разряда равно количеству деревьев ранга <tex>i</tex>, присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга <tex>i</tex> содержит ровно <tex>3^i</tex> узлов.
Заметим, что состояние избыточного корневого представления определяется неоднозначно. Очевидно, что для любой толстой кучи, состоящей из <tex>n</tex> элементов, существует регулярное избыточное представление корневого счетчика.
Списочный элемент, приписанный <tex>i</tex>-му разряду избыточного корневого представления, — это указатель на список деревьев ранга <tex>i</tex>, присутствующих в куче, образованный посредством указателей <tex>Right</tex> корневых узлов связываемых деревьев.
{{Утверждение
|id=proposal2.
|author=
|about=о корневом счетчике
|statement=
Из определения корневого счетчика следует:
*Корневой счетчик позволяет иметь доступ к корню любого дерева ранга <tex>i</tex> за время <tex>O(1)</tex>.
*Вставка толстого дерева ранга <tex>i</tex> соответствует операции инкрементирования <tex>i</tex>-го разряда корневого счетчика.
*Удаление толстого поддерева ранга <tex>i</tex> соответствует операции декрементирования <tex>i</tex>-го разряда корневого счетчика.
*Операции инкрементирования и декрементирования <tex>i</tex>-го разряда корневого счетчика осуществляются за время <tex>O(1)</tex>.
|proof=
}}
'''корневой счетчик''' представляем расширяющимся массивом <tex>RootCount</tex> , каждый элемент которого — запись с тремя полями:
*<tex>RootCount[i].Value</tex> {{---}} <tex>i</tex>-й разряд равный количеству деревьев ранга <tex>i</tex>.
*<tex>RootCount[i].ForvardPointer</tex> {{---}} прямой указатель <tex>i</tex>-го разряда.
*<tex>RootCount[i].ListPointer</tex> {{---}} указатель на список деревьев ранга <tex>i</tex>, присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя <tex>Right</tex> корневых узлов связываемых деревьев. Если в куче нет деревьев ранга <tex>i</tex> , то указатель <tex>ListPointer</tex> равен NULL. Заметим, что если значение равно нулю, то нам неважно значение указателя <tex>RootCount[i].ListPointer</tex>.
=Основные операции=
