Толстая куча на избыточном счётчике

Толстое дерево (статья пишется - ничего не трогать!)

Определение:

Определяем толстое дерево [math]F_k[/math] ранга [math]k[/math], [math]k = 0, 1, 2, \dots [/math] следующим образом:

• Толстое дерево [math]F_0[/math] ранга ноль состоит из единственного узла.
  
• Толстое дерево [math]F_k[/math] ранга [math]k[/math], для [math]k = 1, 2, 3,\dots [/math], состоит из трех деревьев [math]F_{k-1}[/math] ранга [math]k[/math], связанных так, что корни двух из них являются самыми левыми потомками корня третьего.

Ранг узла [math]x[/math] в толстом дереве определяется как ранг толстого поддерева с корнем в узле [math]x[/math].

//[[Файл:ThickTreeExample.gif Пример толстых деревьев [math]F_0, F_1, F_2, F_3[/math]]]

Свойства Толстых деревьев

Утверждение:

Свойства толстых деревьев: В толстом дереве ранга [math]k[/math] ровно [math]3^k[/math] узлов. Для любого натурального числа [math]n[/math] существует лес из толстых деревьев, в котором ровно [math]n[/math] узлов. Такой лес можно построить, включив в него столько деревьев ранга [math]i[/math], каково значение [math]i[/math]-го разряда представления числа [math]n[/math] в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления. Толстый лес из [math]n[/math] узлов содержит [math]O(n\log(n))[/math] деревьев.

Определение:

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

Определение:

Узел в нагруженном лесе назовем неправильным, если его ключ меньше ключа его родителя.

Определение:

Нагруженный лес назовем почти кучеобразным, если для каждого значения [math]k[/math] в нем имеется не более двух неправильных узлов ранга [math]k[/math].

Толстые кучи

Определение:

Толстая куча — это почти кучеобразный нагруженный лес.

Представление толстой кучи

Каждый узел толстой кучи будем представлять записью со следующими полями:

• [math]Key[/math] — ключ элемента, приписанного узлу дерева
• [math]Parent[/math] — указатель на родителя
• [math]Lest[/math] — указатель на ближайшего левого брата
• [math]Right[/math] — указатель на ближайшего правого брата
• [math]LChild[/math] — указатель на самого левого сына
• [math]Rank[/math] — ранг узла.

"Братья" связаны в двусвязный список при помощи указателей [math]Left[/math] и [math]Right[/math]. У самого левого (правого) "брата" в этом списке указатель [math]Left[/math] ([math]Right[/math]) равен [math]NULL[/math].

//[[Файл:ThickTreeExample.gif Пример толстых деревьев [math]F_0, F_1, F_2, F_3[/math]]]

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

Нам понадобятся понятия корневого счетчика и счетчика нарушений.

Толстую кучу будем представлять записью следующего вида: [math]FatHeap = (RootCount, CountViolation, Minpointer, MaxRank)[/math], где:

[math]RootCount[/math] — массив, соответствующий корневому счетчику

[math]CountViolation[/math] — массив, соответствующий счетчику нарушений

[math]MinPointer[/math] — указатель на элемент кучи с минимальным ключом

[math]MaxRank[/math] — наибольший ранг среди рангов деревьев, присутствующих в куче

Избыточное представление чисел

Определение:

Избыточным [math]b[/math]-арным представлением числа [math]x[/math] будем называть последовательность [math]d = d_n, d_{n-1}, ... d_0[/math], такую что [math]x = {\sum\limits^{n}_{i = 0} {d_i}}{b^i}[/math] где [math] d_i \in \{0, 1, ..., b\} [/math], [math] i \in \{0, 1, ..., n\} [/math]

Корневой счетчик

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

Значение его [math]i[/math]-го разряда равно количеству деревьев ранга [math]i[/math], присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга [math]i[/math] содержит ровно [math]3^i[/math] узлов. Заметим, что состояние избыточного корневого представления определяется неоднозначно. Очевидно, что для любой толстой кучи, состоящей из [math]n[/math] элементов, существует регулярное избыточное представление корневого счетчика. Списочный элемент, приписанный [math]i[/math]-му разряду избыточного корневого представления, — это указатель на список деревьев ранга [math]i[/math], присутствующих в куче, образованный посредством указателей [math]Right[/math] корневых узлов связываемых деревьев.

Утверждение (о корневом счетчике):

Из определения корневого счетчика следует: Корневой счетчик позволяет иметь доступ к корню любого дерева ранга [math]i[/math] за время [math]O(1)[/math]. Вставка толстого дерева ранга [math]i[/math] соответствует операции инкрементирования [math]i[/math]-го разряда корневого счетчика. Удаление толстого поддерева ранга [math]i[/math] соответствует операции декрементирования [math]i[/math]-го разряда корневого счетчика. Операции инкрементирования и декрементирования [math]i[/math]-го разряда корневого счетчика осуществляются за время [math]O(1)[/math].

корневой счетчик представляем расширяющимся массивом [math]RootCount[/math] , каждый элемент которого — запись с тремя полями:

• [math]RootCount[i].Value[/math] — [math]i[/math]-й разряд равный количеству деревьев ранга [math]i[/math].
• [math]RootCount[i].ForvardPointer[/math] — прямой указатель [math]i[/math]-го разряда.
• [math]RootCount[i].ListPointer[/math] — указатель на список деревьев ранга [math]i[/math], присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя [math]Right[/math] корневых узлов связываемых деревьев. Если в куче нет деревьев ранга [math]i[/math] , то указатель [math]ListPointer[/math] равен NULL.

Заметим, что если значение равно нулю, то нам неважно значение указателя [math]RootCount[i].ListPointer[/math].

Инициализация

Чтобы время инициализации счетчиков было [math]O(1)[/math], используем поразрядную их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную [math]MaxRank[/math], которая показывает нам, какая часть массивов счетчиков используется в данный момент.

При начальной инициализации необходимо установить счетчики в состояние, которое отвечает пустой куче. Очевидно, что в пустой куче не может быть никаких нарушений.

Обновление прямого указателя

Обновление прямого указателя i-го разряда корневого счетчика заключается в выполнении следующего псевдокода:

if (RootCount[i+1].Value=3-1)
    RootCount[i].ForwardPointer := RootCount[i+1].ForwardPointer;
else
    RootCount[i].ForwardPointer := i + 1;

Корректировка при вставке

Корректировка списочной части [math]i[/math]-го разряда корневого счетчика при вставке в кучу нового дерева ранга [math]i[/math] ([math]InsertTree(i,p)[/math]). Эта процедура вставляет новое дерево ранга [math]i[/math] (на него указывает указатель [math]p[/math]) в списочную часть [math]i[/math] -го разряда корневого счетчика [math]RootCount[/math] выглядит так:

p1 := RootCount[i].ListPointer;
if(RootCount[i].Value != 0)
    p.Right = p1;
else
    p.Right = NULL;
p.Left := NULL;
RootCount[i].ListPointer := p;

Корректировка при удалении

Корректировка списочной части [math]i[/math]-го разряда корневого счетчика при удалении из кучи дерева ранга [math]i[/math] ([math]DeleteTree(i,p)[/math]). Эта процедура удаляет дерево ранга [math]i[/math] (на него указывает указатель [math]p[/math]) из списочной части [math]i[/math]-го разряда корневого счетчика [math]RootCount[/math] . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:

p1 := RootCount[i].ListPointer;
if(p1 = p)
    RootCount[i].ListPointer := p.Right;
j:= 1;
while(j<=RootCount[i].Value) and (p1.Right != p) do
    p1.Right = p.Right;

Связывание трех деревьев в одно

Связывание [math](Fastening (p1, p2, p3))[/math] трех толстых деревьев ранга [math]i[/math] в одно толстое дерево ранга [math]i+1[/math]. Эта функция принимает три указателя [math](p1, p2 ,p3)[/math] на три разных толстых дерева одного и того же ранга [math]i[/math] и возвращает указатель на вновь сформированное дерево ранга [math]i+1[/math] . Процедура заключается в выполнении следующего псевдокода:

if(p1.Key<=p2.Key) and (p1.Key<=p3.Key)
    MinP := p1;
    p1 := p2;
    p2 := p3;
if(p2.Key<=p1.Key) and(p2.Key<=p3.Key)
    MinP := p2;
    p1 := p1;
    p2 := p3;
if(p3.Key<=p1.Key) and(p3.Key<=p2.Key)
    MinP := p3;
    p1 := p1;
    p2 := p2;
p1.Right := p2;
p1.Left := NULL;
p1.Parent := MinP;
p2.Right :=MinP.LChild;
p2.Left :=p1;
p2.Parent := MinP;
if(MinP.LChild != NULL)
    MinP.LChild.Left = p2;
MinP.LChild := p1;
MinP.Rank := MinP.Rank+1;
MinP.Right := NULL;
MinP.Left := NULL;
Fastening := MinP; 

Значение ключа элемента по указателю

Функция [math]GetKey(p)[/math] по указателю p на элемент определяет значение его ключа:

if(p = NULL)
    Min := [math]\infty[/math];
else
    Min := p.key;
GetKey := Min; 

Узел с минимальным ключом

Функция [math]MinKeyNodeRoot(p)[/math], которая по указателю [math]p[/math] на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:

p1:=p;
MinP := p1;
while (p1 != NULL) do
    if(p1.Key < MinP.Key)
        MinP := p1;
        p1 := p1.Right;
MinKeyNodeRoot := MinP;

Счетчик нарушений

Заметим, что счетчик нарушений очень похож на корневой счетчик выше, но в отличие от второго:

• Нас теперь интересует не само число, а только значения разрядов.
• Операция фиксации тесно связана с толстой кучей.

Значение [math]i[/math]-го разряда для счетчика нарушений интерпретируется как количество неправильных узлов ранга [math]i[/math] , а его списочная часть — это указатели на неправильные узлы ранга [math]i[/math] .

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

Счетчик нарушений представлен Саморасширяющимся массивом, элементы которого состоят из четырех полей:

• [math]CountViolation[i].Value[/math] — количество неправильных узлов ранга [math]i[/math] в куче.
• [math]CountViolation[i].ForvardPointer[/math] — прямой указатель [math]i[/math]-го разряда
• [math]CountViolation[i].FirstViolation[/math] — указатель на неправильный узел ранга [math]i[/math]
• [math]CountViolation[i].SecondViolation[/math] — указатель на неправильный узел ранга [math]i[/math]

Утверждение (о счетчике нарушений):

из определения счетчика нарушений следует: Наличие счетчика нарушений позволяет иметь доступ к любому неправильному узлу ранга [math]i[/math] за время [math]O(1)[/math] . Уменьшение ключа у элемента ранга [math]i[/math] соответствует операции инкрементирования [math]i[/math]-го разряда счетчика нарушений (естественно, лишь в случае, когда новое значение ключа у изменяемого узла становится меньше значения ключа его родителя). Операции инкрементирования и декрементирования [math]i[/math]-го разряда осуществляются за время [math]O(1)[/math].

Для инициализации нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга [math]MaxRank + 1[/math]. Это первый момент появления в куче узла ранга [math]MaxRank + 1[/math]. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного [math]MaxRank + 1[/math], соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.

Основные операции

• [math]MakeHeap[/math] —[math]O(1)[/math]

заключается в инициализации счетчиков.

• [math]FindMin[/math] —[math]O(1)[/math]

возвращает указатель на минимальный элемент.

• [math]Insert(key)[/math] — [math]O(1)[/math]

Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга [math]0[/math] в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.

• [math]DecreaseKey[/math] — [math]O(1)[/math]

Чтобы выполнить эту операцию, поступим следующим образом. Пусть [math]x[/math] — узел, на который указывает указатель [math]p[/math] . Вычитаем [math]\delta[/math] из ключа узла [math]x[/math] . Если новый ключ [math]x[/math] меньше минимального ключа кучи [math]H[/math], обмениваем ключ элемента [math]p[/math] с ключом минимального элемента. Новых нарушений операция не создаст. Пусть [math]r[/math] — ранг [math]x[/math] . Если [math]x[/math] — нарушаемый узел, добавляем [math]x[/math] как новое [math]r[/math]-ранговое нарушение инкрементированием [math]r[/math]-й цифры [math]d_r[/math] счетчика нарушений.

• [math]DeleteMin[/math] — [math]O(\log(n))[/math]

Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов. Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.

• [math]Delete[/math] — [math]O(\log(n))[/math]

выполняем [math]DecreaseKey[/math] а затем [math]DeleteMin[/math]

• [math]Meld(h1, h2)[/math] — [math]O(\log(n))[/math]

Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — [math]р2[/math] . Пройти по счетчику нарушений [math]p2[/math] от младшей цифры к старшей, пропуская цифры со значением [math]0[/math] . Для [math]i[/math]-й цифры [math]d_i != 0[/math] делаем операцию фиксирования на каждой цифре, показываемой прямым указателем [math]d_i[/math] , если эта цифра имеет значение 2. Затем, если [math]d_i = 2[/math] , фиксируем [math]d_i[/math] . Если [math]d_i = 1[/math] , преобразуем это [math]i[/math]-ранговое нарушение в [math](i+1)[/math]-ранговое нарушение, как при фиксировании, используя [math]i[/math]-рангового брата нарушенного узла вместо (несуществующего) другого [math]i[/math] -рангового нарушения. Как только [math]h2[/math] не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика [math]h2[/math] в корневой счетчик [math]h1[/math] инкрементированием соответствующих цифр. Если минимальный узел [math]h2[/math] содержит меньший ключ, чем минимальный узел [math]h1[/math] , следует установить новым минимальным узлом [math]h1[/math] минимальный узел [math]h2[/math] . Затем нужно вернуть модифицированную кучу [math]h1[/math] в качестве результата [math]Meld[/math] .

• [math]DeleteViolation[/math]

для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:

for i:=0 to h2.MaxRank do
if (CountViolation[i].Value = 2)
    FixCountViolation(i);
for i:=0 to h2.MaxRank do 
    if(CountViolation[i].Value = 1)
        IncCountViolation(i, SearchBrother(CountViolation[i].rmFirstviolation));
        FixCountViolation(i);

Источники

• Толстые кучи — INTUIT.ru