Вспомогательные структуры
Для представления толстой кучи введем новую структуру, которую назовем корневым счетчиком, а для того, чтобы быстро находить неправильные узлы, введем еще один избыточный счетчик, который назовем счетчиком нарушений. Таким образом, толстую кучу можно представить записью следующего вида:
где — массив, соответствующий корневому счетчику; — массив, соответствующий счетчику нарушений; — указатель на элемент кучи, имеющий минимальный ключ; — наибольший ранг среди рангов деревьев, присутствующих в куче.
Корневой счетчик. Корневой счетчик состоит из избыточного троичного представления числа элементов в куче и набора списочных элементов.
Значение -го разряда избыточного корневого представления равно количеству деревьев ранга , присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга содержит ровно узлов. Заметим, что состояние избыточного корневого представления определяется неоднозначно. Отсюда следует, что толстая куча с одним и тем же набором элементов может быть представлена различными наборами толстых деревьев. Очевидно, что для любой толстой кучи, состоящей из элементов, существует регулярное избыточное представление корневого счетчика.
Списочный элемент, приписанный -му разряду избыточного корневого представления, — это указатель на список деревьев ранга , присутствующих в куче, образованный посредством указателей корневых узлов связываемых деревьев.
Определение корневого счетчика дает возможность сделать несколько утверждений:
- Корневой счетчик позволяет иметь доступ к корню любого дерева ранга за время .
- Вставка толстого дерева ранга соответствует операции инкрементирования -го разряда корневого счетчика.
- Удаление толстого поддерева ранга соответствует операции декрементирования -го разряда корневого счетчика.
- Операции инкрементирования и декрементирования -го разряда корневого счетчика осуществляются за время .
Представление корневого счетчика. Корневой счетчик представляем расширяющимся массивом , каждый элемент которого — запись с тремя полями:
которые интерпретируем следующим образом:
- — - й разряд, равный количеству деревьев ранга ;
- — прямой указатель -го разряда;
- — указатель на список деревьев ранга , присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя
корневых узлов связываемых деревьев. Если в куче нет деревьев ранга , то указатель заземлен. Заметим, что если значение равно нулю, то нам неважно, каково значение указателя .
Инициализация корневого счетчика (InitRootCount). Поскольку корневой счетчик реализован как массив записей, возникает вопрос о величине данного массива и о том, что делать, когда весь этот массив заполнен. Чтобы была возможность оценить время инициализации счетчиков величиной , используем поразрядную их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную , которая показывает нам, какая часть массивов счетчиков используется в данный момент.
При начальной инициализации необходимо установить счетчики в состояние, которое отвечает пустой куче. Очевидно, что в пустой куче не может быть никаких нарушений. Операция инициализации выглядит следующим образом.
Обновление прямого указателя i-го разряда корневого счетчика заключается в выполнении операторов
Корректировка списочной части i-го разряда корневого счетчика при вставке в кучу нового дерева ранга i. Эта процедура вставляет новое дерево ранга
(на него указывает указатель ) в списочную часть -го разряда корневого счетчика и заключается в выполнении операторов
Корректировка списочной части i>-го разряда корневого счетчика при удалении из кучи дерева ранга i. Эта процедура удаляет дерево ранга (на него указывает указатель ) из списочной части -го разряда корневого счетчика . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении операторов
Связывание (Fastening (p1, p2, p3)) трех толстых деревьев ранга i в одно толстое дерево ранга i +1.Эта функция принимает три указателя на три разных толстых дерева одного и того же ранга и возвращает указатель на вновь сформированное дерево ранга .
Эта функция принимает три указателя на три разных толстых дерева одного и того же ранга и возвращает указатель на вновь сформированное дерево ранга .
Процедура заключается в выполнении операторов
Функция GetKey (p) по указателю p на элемент определяет значение его ключа и реализуется оператором
Функция MinKeyNodeRoot(p), которая по указателю на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом, реализуется операторами
Очевидно, что трудоемкость всех приведенных выше операций оценивается величиной .
Операция фиксации ({\rm FixRootCount(i)}) Операция фиксации -го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга , состоящий ровно из трех деревьев. При выполнении этой операции значение в -м разряде — должно стать равным нулю, а значение в -м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга , а количество деревьев ранга должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга , связать их в дерево ранга и вставить вновь полученное дерево в кучу.
Следует учесть, что ранг нового дерева может стать больше, чем , что потребует инициализации нового разряда. Для этого необходимо увеличить значение на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
Операция фиксации осуществляется с помощью операторов
Очевидно, что если списочная часть корневого счетчика до операции соответствовала избыточному корневому представлению, то и после операции фиксации это соответствие сохранится. Сохраняется также и регулярность представления. Трудоемкость данной операции .
Инкрементирование i-го разряда корневого счетчика ({\rm IncRootCount(i,p)}). По сравнению с описанным алгоритмом инкрементирования -го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели. Процедура реализуется операторами
Очевидно, что, если корневой счетчик находится в корректном состоянии и , то операция инкрементирования -го разряда корневого счетчика переводит корневой счетчик в новое корректное состояние.
Трудоемкость этой операции равна .
Процедура удаления дерева из кучиподразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг . Тогда значение -го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть. Процедура реализуется операторами
Трудоемкость операции .
Нахождение дерева с минимальным ключом в корне реализуется операторами
Трудоемкость данной операции также .
Счетчик нарушений. К сожалению, здесь не удается разделить работу с избыточным представлением и списочной частью, как в корневом счетчике. Поэтому рассмотрим работу со счетчиком нарушений более подробно. Счетчик нарушений состоит из расширенного избыточного двоичного представления и набора списочных элементов.
Отличие заключается в том, что:
- Нас теперь интересует не само число, а только значения разрядов.
- Операция фиксации тесно связана с толстой кучей.
Значение -го разряда для счетчика нарушений интерпретируется как количество неправильных узлов ранга , а его списочная часть — это указатели на неправильные узлы ранга .
Такое определение счетчика нарушений дает возможность сделать несколько утверждений:
- Наличие счетчика нарушений позволяет иметь доступ к любому неправильному узлу ранга за время .
- Уменьшение ключа у элемента ранга
соответствует операции инкрементирования -го разряда счетчика нарушений (естественно, лишь в случае, когда новое значение ключа у изменяемого узла становится меньше значения ключа его родителя). - Операции инкрементирования и декрементирования -го разряда осуществляются за время .
Представление счетчика нарушений. Счетчик нарушений — это расширяющийся массив, элементы которого являются записями из четырех полей
со следующей интерпретацией:
— количество неправильных узлов ранга в куче, — прямой указатель -го разряда,
и — указатели на неправильные узлы ранга .
Заметим, что если значение
равно единице, то важно лишь значение первого указателя и не играет роли значение второго . Если равно нулю, то неинтересны оба указателя.
Далее ограничимся рассмотрением только наиболее важных операций. Так как счетчик нарушений похож на описанный выше корневой счетчик, акцентируем внимание лишь на различиях. Реализация всех необходимых процедур остается читателю в качестве упражнения.
Инициализация нового звена. Для инициализации нового звена счетчика нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга . Это первый момент появления в куче узла ранга . Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного , соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
