Рассматриваемое в этой лекции представление приоритетной очереди основано
на использовании так называемых избыточных счетчиков, позволяющих за время
O(1) инкрементировать любой разряд. Заметим, что использованные
здесь счетчики — лишь один из способов реализации толстых куч. На самом
деле, для их реализации подойдет произвольный d-арный счетчик, при
условии, что трудоемкость инкрементирования любого его разряда является
константной.
Избыточное представление чисел
Основные определения.
Избыточным $$b$$ -арным
представлением неотрицательного целого числа $$x$$ будем считать
последовательность $$d = d_n$$, $$d_{n-1}\dts d_0$$, такую, что$$\eq*{
x=\suml_{i=0}^{n}d_{i} b^{i},
}$$
где $$d_i \in \{0, 1\dts b\}$$, $$i \in \{0, 1\dts n\}$$.
Будем называть $$d_i$$ цифрой, стоящей в $$i$$ -м
разряде. В примерах запятые между цифрами опускаем.
Заметим, что избыточное представление отличается от обычного $$b$$ -арного представления использованием "лишней"
цифры $$b$$, что
приводит к неоднозначности представления чисел. Например, при $$b =
3$$ число $$3$$ может быть представлено как $$3$$ и
как $$10$$.
В примерах, в которых $$b = 10$$, "цифру" 10 будем
обозначать
символом $$b$$.
Назовем $$b$$ -арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами,
равными $$b$$, найдется цифра, отличная от $$b - 1$$.
Пример.
Пусть $$b = 10$$, а число $$x$$ представляется
в обычной десятичной системе последовательностью $$1100$$, тогда
представления $$b9b$$ и $$bb0$$ не являются регулярными $$b$$ -арными избыточными представлениями числа $$x$$,
а представления $$1100$$ и $$10b0$$ регулярны.
Пусть $$L(i)$$ — номер разряда, отличного от $$b -
1$$ и ближайшего слева от $$i$$ -го разряда в регулярном $$b$$ -арном избыточном представлении $$d$$.
Определим $$L'(i)$$ следующим образом: $$L'(i) = L(i)$$,
если $$d_i \in \{{b - 1}$$, $$b - 2\}$$
и $$d(L(i)) = b$$ ; $$L'(i)$$ — произвольное число $$> i$$, если $$d_i \in \{b - 1, b - 2\}$$
и $$d(L(i)) < b - 1$$ ; $$L'(i)$$ — не определено,
если $$d_i \not\in \{b - 1, b - 2\}$$.
Величину $$L'(i)$$ будем называть прямым указателем.
Пусть $$d = d_n,\ldots, d_0$$ — $$b$$ -арное
регулярное представление
некоторого числа.
Фиксацией цифры b, стоящей в i-м разряде
представления d, $$({\rm Fix (i)})$$
назовем операцию, заключающуюся в обнулении цифры $$d_i$$
и инкрементировании цифры $$d_{i+1}$$, при этом если $$i = n$$, то полагаем $$d_{n+1}= 1$$. При каждом выполнении
операции фиксации будем обновлять значение $$L'(i)$$. Очевидно,
при $$b > 2$$ операцию $${\rm Fix}(i)$$ можно выполнить
с помощью следующих операторов.
$$\formula{
\t if\ d_i = b\ \t then\ \{d_i:= 0;\ d_{i+1}:= d_{i+1}+1\};\\
\t if\ d_{i+1} = b - 1\ \t then\ L'(i):= L'(i+1)\
\t else\ L'(i):= i+1;
}$$
Инкрементирование i-й цифры избыточного
представления d $${\rm Inc (i)}$$ можно выполнить
с помощью операторов
$$\formula{
{\rm Fix}(i);\ \t if\ (d_i = b -1)\
\t{or}\ (d_i = b - 2)\
\t then\ {\rm Fix}(L'(i));\ d_i:= d_i
+ 1;\ {\rm Fix}(i);
}$$
Очевидно, что инкрементирование $$i$$ -го разряда регулярного $$b$$ -арного избыточного представления числа $$x$$
производит представление числа $$x = x + b^i$$.
Нетрудно доказать, что операции фиксации и инкрементирования, примененные
к регулярному избыточному представлению, не нарушают регулярности и
корректно вычисляют указатели $$L$$ с
трудоемкостью $$O(1)$$.
Эта схема может быть расширена для выполнения за константное время
декрементирования произвольной цифры добавлением дополнительного цифрового
значения $$b + 1$$. Оставляем детали в качестве упражнения.
Толстые деревья
Основные определения
Определяем толстое
дерево $$F_k$$ ранга $$k$$ $$(k = 0, 1, 2,\ldots)$$ следующим образом:
Толстое дерево $$F_0$$ ранга ноль состоит из
единственного узла.
Толстое дерево $$F_k$$ ранга $$k$$,
для $$k\ge 1$$, состоит из трех деревьев $$F_{k-1}$$
ранга $$k- 1$$, связанных так, что корни двух из них являются самыми
левыми потомками корня третьего.
Ранг узла $$x$$ в толстом
дереве определяется как ранг толстого поддерева с корнем в узле $$x$$.
На рис. 9.1 приведены примеры толстых деревьев.
(рис 9.1) Свойства толстых деревьев:
В толстом дереве ранга $$k$$ ровно $$3^k$$ узлов.
Для любого натурального числа $$n$$ существует лес из толстых
деревьев, в котором ровно $$n$$ узлов. Такой лес можно построить,
включив в него столько деревьев ранга $$i$$, каково
значение $$i$$ -го разряда представления числа $$n$$ в троичной системе счисления.
Заметим, что для построения такого леса можно использовать и избыточные троичные
представления.
Толстый лес из $$n$$ узлов содержит $$O(\log n)$$ деревьев.
Доказательства этих свойств оставим читателю в качестве упражнения.
Рассмотрим лес из нескольких толстых деревьев, ранги которых не
обязательно попарно различны и узлам которых взаимно однозначно поставлены
в соответствие элементы взвешенного множества. Такой лес будем называть
нагруженным. Узел в нагруженном лесе назовем неправильным, если его ключ
меньше ключа его родителя. Нагруженный лес назовем почти кучеобразным,
если для каждого значения $$k$$ в нем имеется не более двух
неправильных узлов ранга $$k$$.
Толстая куча
Толстая куча — это
почти кучеобразный нагруженный лес.
Представление толстой кучи. Каждый узел толстой кучи будем
представлять записью следующего вида:$$\eq*{
{\rm FatNode} = ({\rm Key}, {\rm Parent}, {\rm Left}, {\rm Right},
{\rm LChild}, {\rm Rank}),
}$$
где $${\rm Key}$$ — ключ элемента, приписанного узлу дерева; $${\rm Parent}$$ — указатель на родителя; $${\rm
Left}$$ — указатель
на ближайшего левого брата; $${\rm Right}$$ — указатель
на ближайшего правого брата; $${\rm LChild}$$ —
указатель на самого левого сына; $${\rm Rank}$$ — ранг узла.
Таким образом, "братья" связаны в двусвязный список при помощи указателей $${\rm Left}$$
и $${\rm Right}$$. У самого левого (правого) "брата"
в этом списке указатель $${\rm Left}$$ ( $${\rm Right}$$ ) заземлен.
На рис. 9.2 представлено толстое дерево $$F_2$$
(внутри узлов указаны их ранги).
(рис 9.2) Вспомогательные структуры
Для представления толстой кучи введем новую структуру, которую назовем
корневым счетчиком, а для того, чтобы быстро находить неправильные узлы,
введем еще один избыточный счетчик, который назовем счетчиком нарушений.
Таким образом, толстую кучу можно представить записью следующего вида:$$\eq*{
{\rm FatHeap} = ({\rm RootCount}, {\rm CountViolation}, {\rm MinPointer},
{\rm MaxRank}),
}$$
где $${\rm RootCount}$$ — массив, соответствующий корневому
счетчику; $${\rm CountViolation}$$ — массив, соответствующий счетчику
нарушений; $${\rm MinPointer}$$ — указатель на элемент кучи, имеющий
минимальный ключ; $${\rm MaxRank}$$ — наибольший ранг среди рангов деревьев,
присутствующих в куче.
Корневой счетчик. Корневой счетчик состоит из избыточного
троичного представления числа элементов в куче и набора списочных
элементов.
Значение $$i$$ -го разряда избыточного корневого представления равно
количеству деревьев ранга $$i$$, присутствующих в куче. При таком
определении избыточного корневого представления число, которое оно
представляет, равно числу узлов в куче, так как толстое дерево
ранга $$i$$ содержит ровно $$3^i$$ узлов. Заметим, что
состояние избыточного корневого представления определяется неоднозначно. Отсюда следует, что
толстая куча с одним и тем же набором элементов может быть представлена
различными наборами толстых деревьев. Очевидно, что для любой толстой
кучи, состоящей из $$n$$ элементов, существует регулярное избыточное
представление корневого счетчика.
Списочный элемент, приписанный $$i$$ -му разряду избыточного
корневого представления, — это указатель на список деревьев ранга $$i$$,
присутствующих в куче, образованный посредством указателей $${\rm
Right}$$ корневых узлов связываемых деревьев.
Определение корневого счетчика дает возможность сделать несколько
утверждений:
Корневой счетчик позволяет иметь доступ к корню любого
дерева ранга $$i$$ за время $$O(1)$$.
Вставка толстого дерева ранга $$i$$ соответствует операции
инкрементирования $$i$$ -го разряда корневого счетчика.
Удаление толстого поддерева ранга $$i$$ соответствует операции
декрементирования $$i$$ -го разряда корневого счетчика.
Операции инкрементирования и декрементирования $$i$$ -го разряда
корневого счетчика осуществляются за время $$O(1)$$.
Представление корневого счетчика. Корневой счетчик
представляем расширяющимся массивом $${\rm RootCount}$$,
каждый элемент которого — запись с тремя полями:$$\eq*{
({\rm Value}, {\rm ForwardPointer}, {\rm ListPointer}),
}$$
которые интерпретируем следующим образом:
$${\rm RootCount}[i].{\rm Value}$$ — $$i$$ -й разряд, равный количеству деревьев ранга $$i$$ ;
$${\rm RootCount}[i].{\rm ForwardPointer}$$ —
прямой указатель $$i$$ -го разряда;
$${\rm RootCount}[i].{\rm ListPointer}$$ —
указатель на список деревьев ранга $$i$$, присутствующих в толстой
куче. Деревья в этом списке связаны при помощи указателя $${\rm Right}$$
корневых узлов связываемых деревьев. Если в куче нет деревьев ранга $$i$$,
то указатель $${\rm ListPointer}$$ заземлен. Заметим, что если
значение $${\rm RootCount}[i].{\rm Value}$$ равно нулю, то нам неважно, каково
значение указателя $${\rm RootCount}[i].{\rm
ListPointer}$$.
Инициализация корневого счетчика (InitRootCount). Поскольку
корневой счетчик реализован как массив записей, возникает вопрос о
величине данного массива и о том, что делать, когда весь этот массив
заполнен. Чтобы была возможность оценить время инициализации счетчиков
величиной $$O(1)$$, используем поразрядную их инициализацию. То есть
будем добавлять новые разряды только тогда, когда возникает такая
необходимость, и при этом инициализировать новый разряд сразу в обоих
счетчиках. Для этого мы вводим переменную $${\rm MaxRank}$$, которая
показывает нам, какая часть массивов счетчиков используется в данный
момент.
При начальной инициализации необходимо установить счетчики в состояние,
которое отвечает пустой куче. Очевидно, что в пустой куче не может быть
никаких нарушений. Операция инициализации выглядит следующим образом.
Обновление прямого указателя i-го разряда корневого счетчика $${\rm
UpdateForwardPointer(i)$$ заключается в выполнении операторов
$$\formula{
\t If\ ({\rm RootCount}[i+1].{\rm
Value} = 3-1)\\
\mbox{}\q \t then\ {\rm
RootCount}[i].{\rm ForwardPointer} :=
{\rm RootCount}[i+1].{\rm ForwardPointer}\\
\mbox{}\q \t else\
\t{RootCount}[i].\t{ForwardPointer}:= i+1;
}$$
Корректировка списочной части i-го разряда корневого счетчика
при вставке в кучу нового дерева ранга i $$({\rm InsertTree(i,p)})$$.
Эта процедура вставляет новое дерево ранга $$i$$
(на него указывает указатель $$p$$ ) в списочную часть $$i$$ -го
разряда корневого счетчика $${\rm RootCount}$$ и заключается
в выполнении операторов
$$\formula{
p1 := {\rm RootCount}[i].{\rm ListPointer};\\
\t if\ ({\rm RootCount}[i].{\rm Value}
\ne 0)\
\t then\ p\t{\^{}.}{\rm Right} := p1\
\t {else}\
p\t{\^{}}.{\rm Right} := {\rm nil};\\
p\t{\^{}.}{\rm Left}:= {\rm nil}; {\rm RootCount}[i].{\rm ListPointer} := p;
}$$
Корректировка списочной части i>-го разряда
корневого счетчика при удалении из кучи дерева
ранга i $$({\rm DeleteTree (i; p))$$. Эта процедура удаляет дерево
ранга $$i$$ (на него указывает указатель $$p$$ ) из списочной
части $$i$$ -го разряда корневого счетчика $${\rm RootCount}$$.
Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении
операторов
$$\formula{
p1:= {\rm RootCount}[i].{\rm ListPointer};\\
\t If\ (p1 = p)\ \t then\
{\rm RootCount}[i].{\rm ListPointer} := p\t{\^{}}.{\rm Right};\\
j:= 1;\\
\t while\ (j \le {\rm
RootCount}[i].{\rm Value})\ \t{and}\
(p1\t{\^{}}.{\rm Right} \ne p)\ \t do\\
\t begin\ j:= j+1;\ p1 :=
p1\t{\^{}.}{\rm Right}\,{\rm End}; \\
p1\t{\^{}.}{\rm Right} := p\t{\^{}}.{\rm Right};
}$$
Связывание (Fastening (p1, p2,
p3)) трех толстых деревьев ранга i в одно толстое
дерево ранга i +1. Эта функция принимает три указателя $$(p1, p2, p3)$$ на три разных толстых дерева одного и того же
ранга $$i$$ и возвращает указатель на вновь сформированное
дерево ранга $$i + 1$$.
Процедура заключается в выполнении операторов
$$\formula{
\t if\ (p1\t{\^{}}.{\rm key} \le
p2\t{\^{}}.{\rm Key})\
\t{and}\ (p1\t{\^{}}.{\rm key} \le p3\t{\^{}}.{\rm Key})\ \t then \\
\{{\rm MinP} := p1;\ p1:=p2;\ p2:=p3\};\\
\t if\ (p2\t{\^{}}.{\rm key} \le
p1\t{\^{}}.{\rm Key})\ \t{and}\
(p2\t{\^{}}.{\rm key} \le p3\t{\^{}}.{\rm Key})\ \t then\\
\{{\rm MinP} := p2;\ p1:= p1;\ p2:= p3\};\\
\t if\ (p3\t{\^{}}.{\rm key} \le
p1\t{\^{}}.{\rm Key})\ \t{and}\
(p3\t{\^{}}.{\rm key} \le p2\t{\^{}}.{\rm Key})\ \t then\\
\mbox{}\q \{{\rm MinP}:= p3;\ p1:= p1;\ p2:= p2\};\\
\mbox{}\q p1\t{\^{}}.{\rm Right} := p2;\ p1\t{\^{}}.{\rm Left} := {\rm nil};\
p1\t{\^{}}.{\rm Parent} := {\rm MinP};\\
\mbox{}\q p2\t{\^{}}.{\rm Right} := {\rm MinP}\t{\^{}}.{\rm LChaild};\
p2\t{\^{}}.{\rm Left} := p1;\ p2\t{\^{}}.{\rm Parent} := {\rm MipP};\\
\mbox{}\q \t{if}\ ({\rm PMin}\t{\^{}}.{\rm LChild} \ne {\rm NiL})\ \t{then}\
{\rm PMin}\t{\^{}}.{\rm LChild}\t{\^{}}.{\rm Left} :=p2;\\
{\rm MinP}\t{\^{}}.{\rm LChaild} := p1;\ {\rm MinP}\t{\^{}}.{\rm Rank}
:= {\rm MinP}\t{\^{}}.{\rm Rank} +1;\\
{\rm PMin}\t{\^{}}.{\rm Right} := {\rm NiL};\ {\rm PMin}\t{\^{}}.{\rm Left}
:={\rm NiL};\ {\rm Fastening}:= {\rm MinP};
}$$
Функция GetKey (p)
по указателю p на элемент определяет значение его ключа и реализуется оператором
$$\formula{
\t if\ (p = {\rm nil})\ \t then\ {\rm Min} := \infty\
\t else\ {\rm Min} := p\t{\^{}}.{\rm
Key};\ {\rm GetKey} :=
{\rm Min};
}$$
Функция MinKeyNodeRoot(p), которая по
указателю $$p$$ на списочную часть разряда корневого
счетчика возвращает указатель на корневой узел
с минимальным ключом, реализуется операторами
$$\formula{
p1:= p;\ {\rm MinP} := p1;\\
\t while\ (p1 \ne {\rm nil})\
\t do\\
\t begin if\ (p1\t{\^{}}.{\rm
Key} < {\rm MinP}\t{\^{}}.{\rm Key})\
\t then\ {\rm MinP} := p1;\ p1:=
p1\t{\^{}}.{\rm Right}\,{\rm End}\\
{\rm MinKeyNodeRoot} := {\rm MinP};
}$$
Очевидно, что трудоемкость всех приведенных выше операций оценивается
величиной $$O(1)$$.
Операция фиксации ({\rm
FixRootCount(i)})
Операция фиксации $$i$$ -го разряда корневого счетчика подразумевает,
что его значение равно трем, а списочная часть содержит указатель
на список деревьев ранга $$i$$, состоящий ровно из трех деревьев.
При выполнении этой операции значение в $$i$$ -м разряде —
должно стать равным нулю, а значение в $$(i + 1)$$ -м разряде увеличиться на
единицу. То есть в куче не должно остаться деревьев ранга $$i$$, а количество
деревьев ранга $$i + 1$$ должно увеличиться на единицу. Для этого
следует удалить из кучи три присутствующих в ней дерева ранга $$i$$,
связать их в дерево ранга $$i + 1$$ и вставить вновь полученное дерево
в кучу.
Следует учесть, что ранг нового дерева может стать больше, чем $${\rm
MaxRank}$$, что потребует инициализации нового разряда. Для этого необходимо увеличить
значение $${\rm MaxRank}$$ на единицу и заполнить новое поле, а также
провести инициализацию нового разряда.
Операция фиксации осуществляется с помощью операторов
$$\formula{
\t if\ ({\rm MaxRank} = i)\ \t then\ \{{\rm MaxRank}:= i+1;\
{\rm RootCount}[i+1]\t{\^{}}.{\rm Value}:= 0;\\
{\rm CountViolation}[i+1].{\rm Value}:= 0\}\\
\mbox{}\q \t else\ \{{\rm
UpdateForwardPointer}(i+1)\};\\
{\rm RootCount}[i].{\rm Value}:= 0;\\
p1:= {\rm RootCount}[i].{\rm ListPointer};\ p2:= p1\t{\^{}}.{\rm Right};\
p3:= p2\t{\^{}}.{\rm Right};\\
p:= {\rm Fastening}(p1, p2, p3);\ {\rm RootCount}[i]\t{\^{}}.
{\rm ListPointer}:= {\rm nil};\\
{\rm InsertTree}(i+1, p); \\
{\rm RootCount}[i+1].{\rm Value}:= {\rm RootCount}[i+1].{\rm Value} + 1;
}$$
Очевидно, что если списочная часть корневого счетчика до операции
соответствовала избыточному корневому представлению, то и после операции
фиксации это соответствие сохранится. Сохраняется также и регулярность
представления. Трудоемкость данной операции $$O(1)$$.
Инкрементирование i-го разряда корневого
счетчика ({\rm IncRootCount(i,p)}). По
сравнению с описанным алгоритмом инкрементирования $$i$$ -го разряда избыточного
представления здесь мы должны учесть работу со списочной частью и обновить
прямые указатели. Процедура реализуется операторами
$$\formula{
\t if\ ({\rm RootCount}[i].{\rm Value}
= 1)\ \t{or}\
({\rm RootCount}[i].{\rm Value} = 2)\\
\mbox{}\q \t then if\
({\rm RootCount}[{\rm RootCount}[i].{\rm ForwardPointer}].{\rm Value} =3)\\
\mbox{}\q\qq \t then\ {\rm
FixRootCount}
({\rm RootCount}[i].{\rm ForwardPointer});\\
\t if\ ({\rm RootCount}[i].{\rm Value}
= 3)\
\t then\ {\rm FixRootCount}(i);\\
{\rm InsertTree}(i,p);\\
{\rm RootCount}[i].{\rm Value}:= {\rm RootCount}[i].{\rm Value} + 1;\\
{\rm UpdateForwardPointer}(I);\\
\t if\ ({\rm RootCount}[i].{\rm Value}
= 3)\ \t then\
{\rm FixRootCount}(i);
}$$
Очевидно, что, если корневой счетчик находится в корректном состоянии
и $$i \le {\rm MaxRank}$$, то операция инкрементирования $$i$$ -го разряда корневого счетчика переводит корневой счетчик в новое корректное
состояние. Трудоемкость этой операции равна $$O(1)$$.
Процедура удаления дерева из кучи подразумевает наличие в куче
этого дерева. Пусть удаляемое дерево имеет ранг $$i$$. Тогда значение $$i$$ -го разряда избыточного корневого представления не равно нулю.
То есть уменьшение этого значения на единицу не испортит регулярности
представления и не потребует обновления каких-либо указателей. Необходимо
лишь соответствующим образом обработать списочную часть. Процедура
реализуется операторами
$$\formula{
{\rm DeleteTree}(i, p);\ {\rm RootCount}[i].{\rm Value}:=
{\rm RootCount}[i].{\rm Value} -1;
}$$
Трудоемкость операции $$O(1)$$.
Нахождение дерева с минимальным
ключом в корне $$({\rm MinKey})$$ реализуется операторами
$$\formula{
{\rm MinP} := {\rm nil};\\
\t for\ i:= 0\ \t to\ {\rm MaxRank}\ \t do \\
\t begin\\
p1 := {\rm MinKeyNodeRoot}\ ({\rm RootCount}[i].{\rm ListPointer});\\
\t if\ ({\rm GetKey}(p1) < {\rm
GetKey}({\rm MinP}))\
\t then\ {\rm MinP}:= p1;\\
\t end;
{\rm MinKey} := {\rm MinP};
}$$
Трудоемкость данной операции также $$O(1)$$.
Счетчик нарушений. К сожалению, здесь не удается разделить
работу с избыточным представлением и списочной частью, как в корневом
счетчике. Поэтому рассмотрим работу со счетчиком нарушений более подробно.
Счетчик нарушений состоит из расширенного избыточного двоичного
представления и набора списочных элементов.
Отличие заключается в том, что:
Нас теперь интересует не само число,
а только значения разрядов.
Операция фиксации тесно связана с толстой кучей.
Значение $$i$$ -го разряда для счетчика нарушений интерпретируется
как
количество неправильных узлов ранга $$i$$, а его списочная часть
— это
указатели на неправильные узлы ранга $$i$$.
Такое определение счетчика нарушений дает возможность сделать несколько
утверждений:
Наличие счетчика нарушений позволяет иметь доступ
к любому неправильному узлу ранга $$i$$ за
время $$O(1)$$.
Уменьшение ключа у элемента ранга $$i$$
соответствует операции инкрементирования $$i$$ -го разряда счетчика
нарушений (естественно, лишь в случае, когда новое значение ключа
у изменяемого узла становится меньше значения ключа его родителя).
Операции инкрементирования и декрементирования $$i$$ -го разряда осуществляются за время $$O(1)$$.
Представление счетчика нарушений.
Счетчик нарушений — это расширяющийся массив, элементы которого являются записями
из четырех полей
$$\eq*{
({\rm Value}, {\rm ForwardPointer}, {\rm FirstViolation},
{\rm SecondViolation})
}$$
со следующей интерпретацией: $${\rm CountViolation}[i].{\rm Value}$$
— количество неправильных узлов ранга $$i$$ в куче, $${\rm CountViolation}[i].{\rm ForwardPointer}$$ — прямой
указатель $$i$$ -го разряда, $${\rm CountViolation}[i].{\rm
FirstViolation}$$
и $${\rm CountViolation}[i].{\rm SecondViolation}$$ — указатели
на неправильные узлы ранга $$i$$.
Заметим, что если значение $${\rm CountViolation}[i].{\rm Value}$$
равно единице, то важно лишь значение первого
указателя $${\rm FirstViolation}$$ и не играет роли значение
второго $${\rm SecondViolation}$$.
Если $${\rm CountViolation}[i].{\rm Value}$$ равно нулю,
то неинтересны оба указателя.
Далее ограничимся рассмотрением только наиболее важных операций. Так как
счетчик нарушений похож на описанный выше корневой счетчик, акцентируем
внимание лишь на различиях. Реализация всех необходимых процедур остается
читателю в качестве упражнения.
Инициализация нового звена.
Для инициализации нового звена счетчика нарушений необходимо лишь занулить его значение в новом разряде.
Делается это только тогда, когда мы вводим в кучу новое дерево
ранга $${\rm MaxRank} + 1$$. Это первый момент появления
в куче узла ранга $${\rm MaxRank} + 1$$.
Для тех нарушений, которые могут возникнуть в узлах ранга меньше
либо равного $${\rm MaxRank} + 1$$, соответствующие разряды счетчика
нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
Вспомогательные процедуры
Процедура обновления прямого указателя $$i$$ -го разряда счетчика
нарушений аналогична процедуре $${\rm UpdateForwardPointer}(i)$$
для корневого счетчика. Необходимо лишь учесть, что
счетчик нарушений — двоичный.
Процедура корректировки списочной части $$i$$ -го разряда
счетчика нарушений при появлении в куче нового $$i$$ -рангового
нарушения — назовем ее $${\rm InsertViolation}(i;{\rm pNode})$$
— вставляет новый нарушенный узел, обновляя, в зависимости
от значения $${\rm CountViolation}[i].{\rm Value}$$,
либо первый $$({\rm FirstViolation})$$, либо
второй $$({\rm SecondViolation})$$ указатель.
Причем перед тем как вставлять в счетчик новое нарушение,
необходимо проверить, не присутствует ли оно там.
Процедура взаимной замены поддеревьев кучи с корнями
в узлах $$p1$$ и $$p2$$ — назовем ее $${\rm
InterChange}(p1,p2)$$ —
подразумевает, что ранги обмениваемых деревьев одинаковы.
Также нам необходима функция $${\rm SearchBrother}(p)$$,
которая возвращает указатель на брата того же ранга,
что и передаваемый ей узел. Она проверяет ранги своего
правого и левого братьев (если такие существуют) и возвращает
указатель на брата того же ранга (он существует обязательно).
Функция, которая связывает три толстых дерева ранга $$i$$ в одно
толстое дерево ранга $$i + 1$$, аналогична соответствующей функции
для корневого счетчика.
Функция, которая возвращает указатель на минимальный нарушенный
узел ранга $$i$$ среди элементов $$i$$ -го разряда счетчика
нарушений. Если $$i$$ -й разряд счетчика нарушений пуст,
то возвращается $${\rm nil}$$.
Как и в случае корневого счетчика, все операции выполняются
за константное время.
Свойство регулярности. Определим свойство регулярности для
счетчика нарушений. Назовем состояние счетчика нарушений регулярным, если
между любыми двумя цифрами, равными двум, существует цифра, отличная от
единицы. Неправильный узел ранга $$i$$ в дальнейшем будем называть $$i$$ -ранговым нарушением.
Операция фиксации. Фиксация $$i$$ -й цифры $$d_i = 2$$
соответствует либо преобразованию двух $$i$$ -ранговых нарушений в одно $$(i + 1)$$ -ранговое нарушение, либо устранению обоих $$i$$ -ранговых нарушений. Проводить эту операцию предлагается следующим образом.
Упорядочиваем два $$i$$ -ранговых нарушения так, чтобы они имели
одного родителя (очевидно, что в общем случае $$i$$ -ранговые нарушения могут
иметь разных родителей). Сделать это предлагается заменой поддерева
с корнем в нарушенном узле, чей родитель имеет меньший ключ, на поддерево с
корнем в $$i$$ -ранговом брате нарушаемого узла, чей родитель имеет
больший ключ. Легко убедиться, что такая замена не приводит к созданию
новых нарушений. Пусть узел $$y$$ — общий родитель двух
нарушаемых узлов после замены — принадлежит дереву $$F$$.
Разобьем дальнейшее рассмотрение на два случая:
Ранг $$y$$ равен $$i + 1$$. Пусть $$F_1$$ и $$F_2$$ — это толстые деревья
ранга $$i$$ с корнями в двух нарушаемых узлах,
а дерево $$F^y$$ — толстое дерево
ранга $$i$$, полученное из поддерева с корнем в узле $$y$$
удалением поддеревьев $$F^1$$ и $$F^2$$.Если узел $$y$$ не является корнем дерева $$F$$, то
удаляем из дерева $$F$$
поддерево $$F^y$$. Из трех толстых деревьев $$(F, F^1, F^2$$ )
ранга $$i$$ образуем одно дерево ранга $$i + 1$$, чей
корень $$z$$ является узлом с наименьшим ключом среди корней деревьев $$F, F^1, F^2$$. Вставляем в дерево $$F$$ вновь полученное
толстое дерево с корнем в узле $$z$$ вместо поддерева с корнем в
узле $$y$$. Если узел $$z$$ оказывается нарушенным,
инкрементируем $$d_{i+1}$$.
Значение $$i$$ -го разряда делаем нулевым.
Если узел $$y$$ — корень дерева $$F$$, то удаляем
дерево $$F$$ из кучи. Из трех толстых деревьев $$(F, F^1, F^2)$$
ранга $$i$$ образуем одно дерево ранга $$i$$, чей
корень $$z$$ является узлом
с наименьшим ключом среди ключей корней деревьев $$F, F^1, F^2$$.
Вставляем вновь полученное толстое дерево с корнем в узле $$z$$
в кучу. Значение $$i$$ -го разряда делаем нулевым.
Если ранг $$y$$ больше, чем $$i + 1$$, то, по условию
регулярности счетчика нарушений, узел $$y$$ должен иметь хотя бы одного
сына $$w$$ ранга $$i + 1$$, который не является $$(i +
1)$$ -ранговым нарушением, и два $$i$$ -ранговых сына $$w$$ должны быть
также ненарушенными.
Тогда заменяем два нарушенных $$i$$ -ранговых сына
узла $$y$$ на два хороших $$i$$ -ранговых сына
узла $$w$$. Тем самым мы свели задачу к случаю 1.
Можно доказать, что рассматриваемая операция не испортит регулярности
счетчика.
Инкрементирование i-го разряда счетчика
нарушений $$({\rm IncCount Violation(i,p)}).$$
Используя описанную выше операцию фиксации, можно
осуществить инкрементирование $$i$$ -го разряда счетчика нарушений
следующими операторами:
$$\formula{
{\rm FixCountViolation} (i);\\
{\rm FixCountViolation} ({\rm CountViolation} [i]\t{\^{}}.
{\rm ForwardPointer});\\
\mbox{}\q {\rm InsertViolation}(i, {\rm pNode});\\
{\rm CountViolation}[i].{\rm Value}:= {\rm CountViolation}[i].{\rm Value} +
1;\\
{\rm FixCountViolation} (i);\\
{\rm FixCountViolation}\ ({\rm CountViolation} [i]\t{\^{}}.
{\rm ForwardPointer});
}$$
Трудоемкость операции $$O(1)$$.
Удаление нарушения из кучи.
Заметим, что удаление нарушения из кучи подразумевает наличие в куче этого нарушения; пусть это нарушение
ранга $$i$$. Тогда значение $$i$$ -го разряда для счетчика
нарушений не равно нулю. Следовательно, уменьшение этого значения на единицу не
испортит регулярности и не потребует обновления каких-либо указателей.
Необходимо лишь уменьшить на единицу значение переменной $${\rm CountViolation} [i].{\rm Value}$$ и обработать указатели $${\rm FirstViolation}$$ и $${\rm SecondViolation}$$.
Очевидно, что трудоемкость этой операции $$O(1)$$.
Нахождение узла с минимальным
значением ключа среди всех нарушений.
Для реализации этой функции предлагается перебрать все
нарушения до максимального ранга и найти среди них узел с минимальным
весом. Трудоемкость данной операции $$O(\log n)$$.
Основные операции
Операция make-heap
заключается в инициализации счетчиков. Трудоемкость $$O(1)$$.
Операция FindMin возвращает указатель
на минимальный элемент. Трудоемкость $$O(1)$$.
Операция Insert(key).
Чтобы выполнить эту операцию, делаем новый элемент отдельным
деревом и выполняем процедуру вставки нового элемента ранга $$0$$ в
корневой счетчик. После этого, если необходимо, корректируем значение указателя на
минимальный элемент.
Операция уменьшения ключа
DecreaseKey.
Чтобы выполнить эту операцию, поступим следующим образом.
Пусть $$x$$ — узел, на который указывает указатель $$p$$.
Вычитаем $$\Dl$$ из ключа узла $$x$$. Если новый
ключ $$x$$ меньше минимального ключа кучи $$H$$,
обмениваем ключ элемента $$p$$ с ключом минимального элемента. Новых
нарушений операция не создаст. Пусть $$r$$ — ранг $$x$$.
Если $$x$$ — нарушаемый узел, добавляем $$x$$ как
новое $$r$$ -ранговое нарушение
инкрементированием $$r$$ -й цифры $$d_r$$ счетчика нарушений.
Трудоемкость $$O(1)$$.
Операция DeleteMin
выполняется следующим образом. Удаляем поддерево с корнем в минимальном узле из леса.
Минимальность этого элемента гарантирует нам, что среди его детей
нарушений порядка кучи не было. То есть нет необходимости работать со
счетчиком нарушений. Затем вставляем в кучу все деревья с корнями,
расположенными в детях удаляемого узла. Очевидно, что новый минимальный
ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск
нового минимального элемента среди корней деревьев и нарушенных узлов.
Если минимальный элемент оказался в нарушенном узле, то обмениваем его
с элементом, хранимым в корне этого дерева, корректируя корневой счетчик,
если это необходимо. После замены новый минимум — в корне дерева леса.
Этот корень будет новым минимальным узлом. Трудоемкость операции
равна $$O(\log n)$$.
Операция удаления элемента.
Выполняется с помощью $${\rm DecreaseKey}$$ и затем $${\rm DeleteMin}$$. Трудоемкость
операции $$O(\log n)$$.
Операция Meld(h1, h2).
Выполняется следующим образом. Первый
шаг — фиксируются все нарушения в куче с меньшим максимальным рангом
(разрывая связь произвольно). Не уменьшая общности, считаем, что эта
куча — $$h2$$. Пройти по счетчику нарушений $$h2$$ от
младшей цифры к старшей, пропуская цифры со значением $$0$$. Для $$i$$ -й
цифры $$d_i \ne 0$$ делаем операцию фиксирования на каждой цифре,
показываемой прямым указателем $$d_i$$, если эта цифра имеет значение 2. Затем,
если $$d_i = 2$$, фиксируем $$d_i$$. Если $$d_i = 1$$,
преобразуем это $$i$$ -ранговое нарушение в $$(i +
1)$$ -ранговое нарушение, как при фиксировании, используя $$i$$ -рангового брата
нарушенного узла вместо (несуществующего) другого $$i$$ -рангового
нарушения.
Как только $$h2$$ не будет содержать каких-либо нарушений, нужно
вставить корни из корневого счетчика $$h2$$ в корневой
счетчик $$h1$$ инкрементированием соответствующих цифр. Если
минимальный узел $$h2$$ содержит меньший ключ, чем минимальный
узел $$h1$$, следует установить
новым минимальным узлом $$h1$$ минимальный узел $$h2$$. Затем
нужно вернуть модифицированную кучу $$h1$$ в качестве результата $${\rm
Meld}$$. Трудоемкость операции равна $$O(\log n)$$.
Операция DeleteViolation. Для освобождения кучи от нарушений
достаточно выполнить операторы
$$\formula{
\t for\ i:= 0\ \t{to}\ h2\t{\^{}}.{\rm
MaxRank}\ \t do\\
\t if\ ({\rm CountViolation}[i].{\rm
Value} = 2)\
\t then\ {\rm FixCountViolation}(i);\\
\t for\ i:= 0\ \t{to}\ h2\t{\^{}}.{\rm
MaxRank}\ \t do\
\t if\ ({\rm CountViolation}[i].{\rm
Value} = 1)\ \t then \\
\{{\rm IncCountViolation}(i, {\rm SearchBrother}
({\rm CountViolation}[i].{\\rm FirstViolation}));\\
{\rm FixCountViolation}(i)\};
}$$
Основываясь на описанной выше реализации толстой кучи, получаем следующий
результат. В толстых кучах операции $${\rm FindMin}, {\rm
Insert}$$ и $${\rm DecreaseKey}$$ выполняются за
время $$O(1)$$,
а $${\rm Delete}, {\rm DeleteMin}$$ и $${\rm Meld}$$ — за
время $$O(\log n)$$.
Замечание.
Существует альтернативное представление избыточных
счетчиков. Вместо одной записи на цифру можно использовать одну запись на
блок одинаковых цифр. Инкрементирование любой цифры можно выполнить за
время $$O(1)$$, используя это альтернативное представление.
Преимущество такого представления — возможность расширить счетчик на произвольное
число одинаковых цифр за постоянное время.
Г.Бродал описывает кучевидную структуру, которая теоретически лучше, чем
толстые кучи, так как их временная оценка
для $${\rm Meld}$$ — $$O(1)$$ в худшем случае. Структура
Бродала, однако, намного сложнее толстых куч.
Сводные сведения о трудоемкости операций с приоритетными
очередями
1.Трудоемкость операций над различными реализациями приоритетной
очереди в худшем случае
| Операции |
$$d$$ -куча |
Левосторонняя куча |
Ленивая левосторонняя куча |
Самоорганизующаяся куча |
Биномиальная очередь |
Ленивая биномиальная очередь |
Фибоначчиева куча |
Слаборастущая куча (run-relaxed) |
Куча Бродала |
|---|
| ВСТАВИТЬ |
$$O(\log_d n)$$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(n) $$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(1) $$ |
| МИН |
$$O(1)$$ |
$$O(1)$$ |
$$O(F)^\ast$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
| УДАЛИТЬ МИН |
$$O(d \log_d n)$$ |
$$O(\log n)$$ |
$$O(F)^\ast$$ |
$$O(n)$$ |
$$O(\log n)$$ |
$$O(n)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
| УДАЛИТЬ |
$$O(d \log_d n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
| УМЕНЬШИТЬ КЛЮЧ |
$$O(\log_d n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$\ldots$$ |
$$O(1)$$ |
$$O(1)$$ |
| СЛИТЬ |
$$-$$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
|
$$O(\log n)$$ |
$$O(1)$$ |
| ОБРАЗОВАТЬ ОЧЕРЕДЬ |
$$O(n)$$ |
$$O(n)$$ |
$$O(n)$$ |
$$\ldots$$ |
$$O(n)$$ |
|
|
$$O(1)$$ |
$$O(1)$$ |
$$^\ast\, F = k \max \{1,\log (n/(k + 1))\}$$
2. Амортизационная трудоемкость выполнения операций
| Операции |
$$d$$ -куча |
Левосторонняя куча |
Ленивая левосторонняя куча |
Самоорганизующаяся куча |
Биномиальная очередь |
Ленивая биномиальная очередь |
Фибоначчиева куча |
Слаборастущая куча (run-relaxed) |
Куча Бродала |
|---|
| ВСТАВИТЬ |
$$O(\log_d n)$$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(1) $$ |
| МИН |
$$O(1)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
| УДАЛИТЬ МИН |
$$O(d \log_d n)$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
| УДАЛИТЬ |
$$O(d \log_d n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
| УМЕНЬШИТЬ КЛЮЧ |
$$O(\log_d n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
| СЛИТЬ |
$$-$$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(\log n)$$ |
| ОБРАЗОВАТЬ ОЧЕРЕДЬ |
$$O(n)$$ |
$$O(n)$$ |
$$O(n)$$ |
$$\ldots$$ |
$$O(n)$$ |
|
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
Рассматриваемое в этой лекции представление приоритетной очереди основано
на использовании так называемых избыточных счетчиков, позволяющих за время
O(1) инкрементировать любой разряд. Заметим, что использованные
здесь счетчики — лишь один из способов реализации толстых куч. На самом
деле, для их реализации подойдет произвольный d-арный счетчик, при
условии, что трудоемкость инкрементирования любого его разряда является
константной.
Избыточное представление чисел
Основные определения.
Избыточным $$b$$ -арным
представлением неотрицательного целого числа $$x$$ будем считать
последовательность $$d = d_n$$, $$d_{n-1}\dts d_0$$, такую, что$$\eq*{
x=\suml_{i=0}^{n}d_{i} b^{i},
}$$
где $$d_i \in \{0, 1\dts b\}$$, $$i \in \{0, 1\dts n\}$$.
Будем называть $$d_i$$ цифрой, стоящей в $$i$$ -м
разряде. В примерах запятые между цифрами опускаем.
Заметим, что избыточное представление отличается от обычного $$b$$ -арного представления использованием "лишней"
цифры $$b$$, что
приводит к неоднозначности представления чисел. Например, при $$b =
3$$ число $$3$$ может быть представлено как $$3$$ и
как $$10$$.
В примерах, в которых $$b = 10$$, "цифру" 10 будем
обозначать
символом $$b$$.
Назовем $$b$$ -арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами,
равными $$b$$, найдется цифра, отличная от $$b - 1$$.
Пример.
Пусть $$b = 10$$, а число $$x$$ представляется
в обычной десятичной системе последовательностью $$1100$$, тогда
представления $$b9b$$ и $$bb0$$ не являются регулярными $$b$$ -арными избыточными представлениями числа $$x$$,
а представления $$1100$$ и $$10b0$$ регулярны.
Пусть $$L(i)$$ — номер разряда, отличного от $$b -
1$$ и ближайшего слева от $$i$$ -го разряда в регулярном $$b$$ -арном избыточном представлении $$d$$.
Определим $$L'(i)$$ следующим образом: $$L'(i) = L(i)$$,
если $$d_i \in \{{b - 1}$$, $$b - 2\}$$
и $$d(L(i)) = b$$ ; $$L'(i)$$ — произвольное число $$> i$$, если $$d_i \in \{b - 1, b - 2\}$$
и $$d(L(i)) < b - 1$$ ; $$L'(i)$$ — не определено,
если $$d_i \not\in \{b - 1, b - 2\}$$.
Величину $$L'(i)$$ будем называть прямым указателем.
Пусть $$d = d_n,\ldots, d_0$$ — $$b$$ -арное
регулярное представление
некоторого числа.
Фиксацией цифры b, стоящей в i-м разряде
представления d, $$({\rm Fix (i)})$$
назовем операцию, заключающуюся в обнулении цифры $$d_i$$
и инкрементировании цифры $$d_{i+1}$$, при этом если $$i = n$$, то полагаем $$d_{n+1}= 1$$. При каждом выполнении
операции фиксации будем обновлять значение $$L'(i)$$. Очевидно,
при $$b > 2$$ операцию $${\rm Fix}(i)$$ можно выполнить
с помощью следующих операторов.
$$\formula{
\t if\ d_i = b\ \t then\ \{d_i:= 0;\ d_{i+1}:= d_{i+1}+1\};\\
\t if\ d_{i+1} = b - 1\ \t then\ L'(i):= L'(i+1)\
\t else\ L'(i):= i+1;
}$$
Инкрементирование i-й цифры избыточного
представления d $${\rm Inc (i)}$$ можно выполнить
с помощью операторов
$$\formula{
{\rm Fix}(i);\ \t if\ (d_i = b -1)\
\t{or}\ (d_i = b - 2)\
\t then\ {\rm Fix}(L'(i));\ d_i:= d_i
+ 1;\ {\rm Fix}(i);
}$$
Очевидно, что инкрементирование $$i$$ -го разряда регулярного $$b$$ -арного избыточного представления числа $$x$$
производит представление числа $$x = x + b^i$$.
Нетрудно доказать, что операции фиксации и инкрементирования, примененные
к регулярному избыточному представлению, не нарушают регулярности и
корректно вычисляют указатели $$L$$ с
трудоемкостью $$O(1)$$.
Эта схема может быть расширена для выполнения за константное время
декрементирования произвольной цифры добавлением дополнительного цифрового
значения $$b + 1$$. Оставляем детали в качестве упражнения.
Толстые деревья
Основные определения
Определяем толстое
дерево $$F_k$$ ранга $$k$$ $$(k = 0, 1, 2,\ldots)$$ следующим образом:
Толстое дерево $$F_0$$ ранга ноль состоит из
единственного узла.
Толстое дерево $$F_k$$ ранга $$k$$,
для $$k\ge 1$$, состоит из трех деревьев $$F_{k-1}$$
ранга $$k- 1$$, связанных так, что корни двух из них являются самыми
левыми потомками корня третьего.
Ранг узла $$x$$ в толстом
дереве определяется как ранг толстого поддерева с корнем в узле $$x$$.
На рис. 9.1 приведены примеры толстых деревьев.
(рис 9.1) Свойства толстых деревьев:
В толстом дереве ранга $$k$$ ровно $$3^k$$ узлов.
Для любого натурального числа $$n$$ существует лес из толстых
деревьев, в котором ровно $$n$$ узлов. Такой лес можно построить,
включив в него столько деревьев ранга $$i$$, каково
значение $$i$$ -го разряда представления числа $$n$$ в троичной системе счисления.
Заметим, что для построения такого леса можно использовать и избыточные троичные
представления.
Толстый лес из $$n$$ узлов содержит $$O(\log n)$$ деревьев.
Доказательства этих свойств оставим читателю в качестве упражнения.
Рассмотрим лес из нескольких толстых деревьев, ранги которых не
обязательно попарно различны и узлам которых взаимно однозначно поставлены
в соответствие элементы взвешенного множества. Такой лес будем называть
нагруженным. Узел в нагруженном лесе назовем неправильным, если его ключ
меньше ключа его родителя. Нагруженный лес назовем почти кучеобразным,
если для каждого значения $$k$$ в нем имеется не более двух
неправильных узлов ранга $$k$$.
Толстая куча
Толстая куча — это
почти кучеобразный нагруженный лес.
Представление толстой кучи. Каждый узел толстой кучи будем
представлять записью следующего вида:$$\eq*{
{\rm FatNode} = ({\rm Key}, {\rm Parent}, {\rm Left}, {\rm Right},
{\rm LChild}, {\rm Rank}),
}$$
где $${\rm Key}$$ — ключ элемента, приписанного узлу дерева; $${\rm Parent}$$ — указатель на родителя; $${\rm
Left}$$ — указатель
на ближайшего левого брата; $${\rm Right}$$ — указатель
на ближайшего правого брата; $${\rm LChild}$$ —
указатель на самого левого сына; $${\rm Rank}$$ — ранг узла.
Таким образом, "братья" связаны в двусвязный список при помощи указателей $${\rm Left}$$
и $${\rm Right}$$. У самого левого (правого) "брата"
в этом списке указатель $${\rm Left}$$ ( $${\rm Right}$$ ) заземлен.
На рис. 9.2 представлено толстое дерево $$F_2$$
(внутри узлов указаны их ранги).
(рис 9.2) Вспомогательные структуры
Для представления толстой кучи введем новую структуру, которую назовем
корневым счетчиком, а для того, чтобы быстро находить неправильные узлы,
введем еще один избыточный счетчик, который назовем счетчиком нарушений.
Таким образом, толстую кучу можно представить записью следующего вида:$$\eq*{
{\rm FatHeap} = ({\rm RootCount}, {\rm CountViolation}, {\rm MinPointer},
{\rm MaxRank}),
}$$
где $${\rm RootCount}$$ — массив, соответствующий корневому
счетчику; $${\rm CountViolation}$$ — массив, соответствующий счетчику
нарушений; $${\rm MinPointer}$$ — указатель на элемент кучи, имеющий
минимальный ключ; $${\rm MaxRank}$$ — наибольший ранг среди рангов деревьев,
присутствующих в куче.
Корневой счетчик. Корневой счетчик состоит из избыточного
троичного представления числа элементов в куче и набора списочных
элементов.
Значение $$i$$ -го разряда избыточного корневого представления равно
количеству деревьев ранга $$i$$, присутствующих в куче. При таком
определении избыточного корневого представления число, которое оно
представляет, равно числу узлов в куче, так как толстое дерево
ранга $$i$$ содержит ровно $$3^i$$ узлов. Заметим, что
состояние избыточного корневого представления определяется неоднозначно. Отсюда следует, что
толстая куча с одним и тем же набором элементов может быть представлена
различными наборами толстых деревьев. Очевидно, что для любой толстой
кучи, состоящей из $$n$$ элементов, существует регулярное избыточное
представление корневого счетчика.
Списочный элемент, приписанный $$i$$ -му разряду избыточного
корневого представления, — это указатель на список деревьев ранга $$i$$,
присутствующих в куче, образованный посредством указателей $${\rm
Right}$$ корневых узлов связываемых деревьев.
Определение корневого счетчика дает возможность сделать несколько
утверждений:
Корневой счетчик позволяет иметь доступ к корню любого
дерева ранга $$i$$ за время $$O(1)$$.
Вставка толстого дерева ранга $$i$$ соответствует операции
инкрементирования $$i$$ -го разряда корневого счетчика.
Удаление толстого поддерева ранга $$i$$ соответствует операции
декрементирования $$i$$ -го разряда корневого счетчика.
Операции инкрементирования и декрементирования $$i$$ -го разряда
корневого счетчика осуществляются за время $$O(1)$$.
Представление корневого счетчика. Корневой счетчик
представляем расширяющимся массивом $${\rm RootCount}$$,
каждый элемент которого — запись с тремя полями:$$\eq*{
({\rm Value}, {\rm ForwardPointer}, {\rm ListPointer}),
}$$
которые интерпретируем следующим образом:
$${\rm RootCount}[i].{\rm Value}$$ — $$i$$ -й разряд, равный количеству деревьев ранга $$i$$ ;
$${\rm RootCount}[i].{\rm ForwardPointer}$$ —
прямой указатель $$i$$ -го разряда;
$${\rm RootCount}[i].{\rm ListPointer}$$ —
указатель на список деревьев ранга $$i$$, присутствующих в толстой
куче. Деревья в этом списке связаны при помощи указателя $${\rm Right}$$
корневых узлов связываемых деревьев. Если в куче нет деревьев ранга $$i$$,
то указатель $${\rm ListPointer}$$ заземлен. Заметим, что если
значение $${\rm RootCount}[i].{\rm Value}$$ равно нулю, то нам неважно, каково
значение указателя $${\rm RootCount}[i].{\rm
ListPointer}$$.
Инициализация корневого счетчика (InitRootCount). Поскольку
корневой счетчик реализован как массив записей, возникает вопрос о
величине данного массива и о том, что делать, когда весь этот массив
заполнен. Чтобы была возможность оценить время инициализации счетчиков
величиной $$O(1)$$, используем поразрядную их инициализацию. То есть
будем добавлять новые разряды только тогда, когда возникает такая
необходимость, и при этом инициализировать новый разряд сразу в обоих
счетчиках. Для этого мы вводим переменную $${\rm MaxRank}$$, которая
показывает нам, какая часть массивов счетчиков используется в данный
момент.
При начальной инициализации необходимо установить счетчики в состояние,
которое отвечает пустой куче. Очевидно, что в пустой куче не может быть
никаких нарушений. Операция инициализации выглядит следующим образом.
Обновление прямого указателя i-го разряда корневого счетчика $${\rm
UpdateForwardPointer(i)$$ заключается в выполнении операторов
$$\formula{
\t If\ ({\rm RootCount}[i+1].{\rm
Value} = 3-1)\\
\mbox{}\q \t then\ {\rm
RootCount}[i].{\rm ForwardPointer} :=
{\rm RootCount}[i+1].{\rm ForwardPointer}\\
\mbox{}\q \t else\
\t{RootCount}[i].\t{ForwardPointer}:= i+1;
}$$
Корректировка списочной части i-го разряда корневого счетчика
при вставке в кучу нового дерева ранга i $$({\rm InsertTree(i,p)})$$.
Эта процедура вставляет новое дерево ранга $$i$$
(на него указывает указатель $$p$$ ) в списочную часть $$i$$ -го
разряда корневого счетчика $${\rm RootCount}$$ и заключается
в выполнении операторов
$$\formula{
p1 := {\rm RootCount}[i].{\rm ListPointer};\\
\t if\ ({\rm RootCount}[i].{\rm Value}
\ne 0)\
\t then\ p\t{\^{}.}{\rm Right} := p1\
\t {else}\
p\t{\^{}}.{\rm Right} := {\rm nil};\\
p\t{\^{}.}{\rm Left}:= {\rm nil}; {\rm RootCount}[i].{\rm ListPointer} := p;
}$$
Корректировка списочной части i>-го разряда
корневого счетчика при удалении из кучи дерева
ранга i $$({\rm DeleteTree (i; p))$$. Эта процедура удаляет дерево
ранга $$i$$ (на него указывает указатель $$p$$ ) из списочной
части $$i$$ -го разряда корневого счетчика $${\rm RootCount}$$.
Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении
операторов
$$\formula{
p1:= {\rm RootCount}[i].{\rm ListPointer};\\
\t If\ (p1 = p)\ \t then\
{\rm RootCount}[i].{\rm ListPointer} := p\t{\^{}}.{\rm Right};\\
j:= 1;\\
\t while\ (j \le {\rm
RootCount}[i].{\rm Value})\ \t{and}\
(p1\t{\^{}}.{\rm Right} \ne p)\ \t do\\
\t begin\ j:= j+1;\ p1 :=
p1\t{\^{}.}{\rm Right}\,{\rm End}; \\
p1\t{\^{}.}{\rm Right} := p\t{\^{}}.{\rm Right};
}$$
Связывание (Fastening (p1, p2,
p3)) трех толстых деревьев ранга i в одно толстое
дерево ранга i +1. Эта функция принимает три указателя $$(p1, p2, p3)$$ на три разных толстых дерева одного и того же
ранга $$i$$ и возвращает указатель на вновь сформированное
дерево ранга $$i + 1$$.
Процедура заключается в выполнении операторов
$$\formula{
\t if\ (p1\t{\^{}}.{\rm key} \le
p2\t{\^{}}.{\rm Key})\
\t{and}\ (p1\t{\^{}}.{\rm key} \le p3\t{\^{}}.{\rm Key})\ \t then \\
\{{\rm MinP} := p1;\ p1:=p2;\ p2:=p3\};\\
\t if\ (p2\t{\^{}}.{\rm key} \le
p1\t{\^{}}.{\rm Key})\ \t{and}\
(p2\t{\^{}}.{\rm key} \le p3\t{\^{}}.{\rm Key})\ \t then\\
\{{\rm MinP} := p2;\ p1:= p1;\ p2:= p3\};\\
\t if\ (p3\t{\^{}}.{\rm key} \le
p1\t{\^{}}.{\rm Key})\ \t{and}\
(p3\t{\^{}}.{\rm key} \le p2\t{\^{}}.{\rm Key})\ \t then\\
\mbox{}\q \{{\rm MinP}:= p3;\ p1:= p1;\ p2:= p2\};\\
\mbox{}\q p1\t{\^{}}.{\rm Right} := p2;\ p1\t{\^{}}.{\rm Left} := {\rm nil};\
p1\t{\^{}}.{\rm Parent} := {\rm MinP};\\
\mbox{}\q p2\t{\^{}}.{\rm Right} := {\rm MinP}\t{\^{}}.{\rm LChaild};\
p2\t{\^{}}.{\rm Left} := p1;\ p2\t{\^{}}.{\rm Parent} := {\rm MipP};\\
\mbox{}\q \t{if}\ ({\rm PMin}\t{\^{}}.{\rm LChild} \ne {\rm NiL})\ \t{then}\
{\rm PMin}\t{\^{}}.{\rm LChild}\t{\^{}}.{\rm Left} :=p2;\\
{\rm MinP}\t{\^{}}.{\rm LChaild} := p1;\ {\rm MinP}\t{\^{}}.{\rm Rank}
:= {\rm MinP}\t{\^{}}.{\rm Rank} +1;\\
{\rm PMin}\t{\^{}}.{\rm Right} := {\rm NiL};\ {\rm PMin}\t{\^{}}.{\rm Left}
:={\rm NiL};\ {\rm Fastening}:= {\rm MinP};
}$$
Функция GetKey (p)
по указателю p на элемент определяет значение его ключа и реализуется оператором
$$\formula{
\t if\ (p = {\rm nil})\ \t then\ {\rm Min} := \infty\
\t else\ {\rm Min} := p\t{\^{}}.{\rm
Key};\ {\rm GetKey} :=
{\rm Min};
}$$
Функция MinKeyNodeRoot(p), которая по
указателю $$p$$ на списочную часть разряда корневого
счетчика возвращает указатель на корневой узел
с минимальным ключом, реализуется операторами
$$\formula{
p1:= p;\ {\rm MinP} := p1;\\
\t while\ (p1 \ne {\rm nil})\
\t do\\
\t begin if\ (p1\t{\^{}}.{\rm
Key} < {\rm MinP}\t{\^{}}.{\rm Key})\
\t then\ {\rm MinP} := p1;\ p1:=
p1\t{\^{}}.{\rm Right}\,{\rm End}\\
{\rm MinKeyNodeRoot} := {\rm MinP};
}$$
Очевидно, что трудоемкость всех приведенных выше операций оценивается
величиной $$O(1)$$.
Операция фиксации ({\rm
FixRootCount(i)})
Операция фиксации $$i$$ -го разряда корневого счетчика подразумевает,
что его значение равно трем, а списочная часть содержит указатель
на список деревьев ранга $$i$$, состоящий ровно из трех деревьев.
При выполнении этой операции значение в $$i$$ -м разряде —
должно стать равным нулю, а значение в $$(i + 1)$$ -м разряде увеличиться на
единицу. То есть в куче не должно остаться деревьев ранга $$i$$, а количество
деревьев ранга $$i + 1$$ должно увеличиться на единицу. Для этого
следует удалить из кучи три присутствующих в ней дерева ранга $$i$$,
связать их в дерево ранга $$i + 1$$ и вставить вновь полученное дерево
в кучу.
Следует учесть, что ранг нового дерева может стать больше, чем $${\rm
MaxRank}$$, что потребует инициализации нового разряда. Для этого необходимо увеличить
значение $${\rm MaxRank}$$ на единицу и заполнить новое поле, а также
провести инициализацию нового разряда.
Операция фиксации осуществляется с помощью операторов
$$\formula{
\t if\ ({\rm MaxRank} = i)\ \t then\ \{{\rm MaxRank}:= i+1;\
{\rm RootCount}[i+1]\t{\^{}}.{\rm Value}:= 0;\\
{\rm CountViolation}[i+1].{\rm Value}:= 0\}\\
\mbox{}\q \t else\ \{{\rm
UpdateForwardPointer}(i+1)\};\\
{\rm RootCount}[i].{\rm Value}:= 0;\\
p1:= {\rm RootCount}[i].{\rm ListPointer};\ p2:= p1\t{\^{}}.{\rm Right};\
p3:= p2\t{\^{}}.{\rm Right};\\
p:= {\rm Fastening}(p1, p2, p3);\ {\rm RootCount}[i]\t{\^{}}.
{\rm ListPointer}:= {\rm nil};\\
{\rm InsertTree}(i+1, p); \\
{\rm RootCount}[i+1].{\rm Value}:= {\rm RootCount}[i+1].{\rm Value} + 1;
}$$
Очевидно, что если списочная часть корневого счетчика до операции
соответствовала избыточному корневому представлению, то и после операции
фиксации это соответствие сохранится. Сохраняется также и регулярность
представления. Трудоемкость данной операции $$O(1)$$.
Инкрементирование i-го разряда корневого
счетчика ({\rm IncRootCount(i,p)}). По
сравнению с описанным алгоритмом инкрементирования $$i$$ -го разряда избыточного
представления здесь мы должны учесть работу со списочной частью и обновить
прямые указатели. Процедура реализуется операторами
$$\formula{
\t if\ ({\rm RootCount}[i].{\rm Value}
= 1)\ \t{or}\
({\rm RootCount}[i].{\rm Value} = 2)\\
\mbox{}\q \t then if\
({\rm RootCount}[{\rm RootCount}[i].{\rm ForwardPointer}].{\rm Value} =3)\\
\mbox{}\q\qq \t then\ {\rm
FixRootCount}
({\rm RootCount}[i].{\rm ForwardPointer});\\
\t if\ ({\rm RootCount}[i].{\rm Value}
= 3)\
\t then\ {\rm FixRootCount}(i);\\
{\rm InsertTree}(i,p);\\
{\rm RootCount}[i].{\rm Value}:= {\rm RootCount}[i].{\rm Value} + 1;\\
{\rm UpdateForwardPointer}(I);\\
\t if\ ({\rm RootCount}[i].{\rm Value}
= 3)\ \t then\
{\rm FixRootCount}(i);
}$$
Очевидно, что, если корневой счетчик находится в корректном состоянии
и $$i \le {\rm MaxRank}$$, то операция инкрементирования $$i$$ -го разряда корневого счетчика переводит корневой счетчик в новое корректное
состояние. Трудоемкость этой операции равна $$O(1)$$.
Процедура удаления дерева из кучи подразумевает наличие в куче
этого дерева. Пусть удаляемое дерево имеет ранг $$i$$. Тогда значение $$i$$ -го разряда избыточного корневого представления не равно нулю.
То есть уменьшение этого значения на единицу не испортит регулярности
представления и не потребует обновления каких-либо указателей. Необходимо
лишь соответствующим образом обработать списочную часть. Процедура
реализуется операторами
$$\formula{
{\rm DeleteTree}(i, p);\ {\rm RootCount}[i].{\rm Value}:=
{\rm RootCount}[i].{\rm Value} -1;
}$$
Трудоемкость операции $$O(1)$$.
Нахождение дерева с минимальным
ключом в корне $$({\rm MinKey})$$ реализуется операторами
$$\formula{
{\rm MinP} := {\rm nil};\\
\t for\ i:= 0\ \t to\ {\rm MaxRank}\ \t do \\
\t begin\\
p1 := {\rm MinKeyNodeRoot}\ ({\rm RootCount}[i].{\rm ListPointer});\\
\t if\ ({\rm GetKey}(p1) < {\rm
GetKey}({\rm MinP}))\
\t then\ {\rm MinP}:= p1;\\
\t end;
{\rm MinKey} := {\rm MinP};
}$$
Трудоемкость данной операции также $$O(1)$$.
Счетчик нарушений. К сожалению, здесь не удается разделить
работу с избыточным представлением и списочной частью, как в корневом
счетчике. Поэтому рассмотрим работу со счетчиком нарушений более подробно.
Счетчик нарушений состоит из расширенного избыточного двоичного
представления и набора списочных элементов.
Отличие заключается в том, что:
Нас теперь интересует не само число,
а только значения разрядов.
Операция фиксации тесно связана с толстой кучей.
Значение $$i$$ -го разряда для счетчика нарушений интерпретируется
как
количество неправильных узлов ранга $$i$$, а его списочная часть
— это
указатели на неправильные узлы ранга $$i$$.
Такое определение счетчика нарушений дает возможность сделать несколько
утверждений:
Наличие счетчика нарушений позволяет иметь доступ
к любому неправильному узлу ранга $$i$$ за
время $$O(1)$$.
Уменьшение ключа у элемента ранга $$i$$
соответствует операции инкрементирования $$i$$ -го разряда счетчика
нарушений (естественно, лишь в случае, когда новое значение ключа
у изменяемого узла становится меньше значения ключа его родителя).
Операции инкрементирования и декрементирования $$i$$ -го разряда осуществляются за время $$O(1)$$.
Представление счетчика нарушений.
Счетчик нарушений — это расширяющийся массив, элементы которого являются записями
из четырех полей
$$\eq*{
({\rm Value}, {\rm ForwardPointer}, {\rm FirstViolation},
{\rm SecondViolation})
}$$
со следующей интерпретацией: $${\rm CountViolation}[i].{\rm Value}$$
— количество неправильных узлов ранга $$i$$ в куче, $${\rm CountViolation}[i].{\rm ForwardPointer}$$ — прямой
указатель $$i$$ -го разряда, $${\rm CountViolation}[i].{\rm
FirstViolation}$$
и $${\rm CountViolation}[i].{\rm SecondViolation}$$ — указатели
на неправильные узлы ранга $$i$$.
Заметим, что если значение $${\rm CountViolation}[i].{\rm Value}$$
равно единице, то важно лишь значение первого
указателя $${\rm FirstViolation}$$ и не играет роли значение
второго $${\rm SecondViolation}$$.
Если $${\rm CountViolation}[i].{\rm Value}$$ равно нулю,
то неинтересны оба указателя.
Далее ограничимся рассмотрением только наиболее важных операций. Так как
счетчик нарушений похож на описанный выше корневой счетчик, акцентируем
внимание лишь на различиях. Реализация всех необходимых процедур остается
читателю в качестве упражнения.
Инициализация нового звена.
Для инициализации нового звена счетчика нарушений необходимо лишь занулить его значение в новом разряде.
Делается это только тогда, когда мы вводим в кучу новое дерево
ранга $${\rm MaxRank} + 1$$. Это первый момент появления
в куче узла ранга $${\rm MaxRank} + 1$$.
Для тех нарушений, которые могут возникнуть в узлах ранга меньше
либо равного $${\rm MaxRank} + 1$$, соответствующие разряды счетчика
нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
Вспомогательные процедуры
Процедура обновления прямого указателя $$i$$ -го разряда счетчика
нарушений аналогична процедуре $${\rm UpdateForwardPointer}(i)$$
для корневого счетчика. Необходимо лишь учесть, что
счетчик нарушений — двоичный.
Процедура корректировки списочной части $$i$$ -го разряда
счетчика нарушений при появлении в куче нового $$i$$ -рангового
нарушения — назовем ее $${\rm InsertViolation}(i;{\rm pNode})$$
— вставляет новый нарушенный узел, обновляя, в зависимости
от значения $${\rm CountViolation}[i].{\rm Value}$$,
либо первый $$({\rm FirstViolation})$$, либо
второй $$({\rm SecondViolation})$$ указатель.
Причем перед тем как вставлять в счетчик новое нарушение,
необходимо проверить, не присутствует ли оно там.
Процедура взаимной замены поддеревьев кучи с корнями
в узлах $$p1$$ и $$p2$$ — назовем ее $${\rm
InterChange}(p1,p2)$$ —
подразумевает, что ранги обмениваемых деревьев одинаковы.
Также нам необходима функция $${\rm SearchBrother}(p)$$,
которая возвращает указатель на брата того же ранга,
что и передаваемый ей узел. Она проверяет ранги своего
правого и левого братьев (если такие существуют) и возвращает
указатель на брата того же ранга (он существует обязательно).
Функция, которая связывает три толстых дерева ранга $$i$$ в одно
толстое дерево ранга $$i + 1$$, аналогична соответствующей функции
для корневого счетчика.
Функция, которая возвращает указатель на минимальный нарушенный
узел ранга $$i$$ среди элементов $$i$$ -го разряда счетчика
нарушений. Если $$i$$ -й разряд счетчика нарушений пуст,
то возвращается $${\rm nil}$$.
Как и в случае корневого счетчика, все операции выполняются
за константное время.
Свойство регулярности. Определим свойство регулярности для
счетчика нарушений. Назовем состояние счетчика нарушений регулярным, если
между любыми двумя цифрами, равными двум, существует цифра, отличная от
единицы. Неправильный узел ранга $$i$$ в дальнейшем будем называть $$i$$ -ранговым нарушением.
Операция фиксации. Фиксация $$i$$ -й цифры $$d_i = 2$$
соответствует либо преобразованию двух $$i$$ -ранговых нарушений в одно $$(i + 1)$$ -ранговое нарушение, либо устранению обоих $$i$$ -ранговых нарушений. Проводить эту операцию предлагается следующим образом.
Упорядочиваем два $$i$$ -ранговых нарушения так, чтобы они имели
одного родителя (очевидно, что в общем случае $$i$$ -ранговые нарушения могут
иметь разных родителей). Сделать это предлагается заменой поддерева
с корнем в нарушенном узле, чей родитель имеет меньший ключ, на поддерево с
корнем в $$i$$ -ранговом брате нарушаемого узла, чей родитель имеет
больший ключ. Легко убедиться, что такая замена не приводит к созданию
новых нарушений. Пусть узел $$y$$ — общий родитель двух
нарушаемых узлов после замены — принадлежит дереву $$F$$.
Разобьем дальнейшее рассмотрение на два случая:
Ранг $$y$$ равен $$i + 1$$. Пусть $$F_1$$ и $$F_2$$ — это толстые деревья
ранга $$i$$ с корнями в двух нарушаемых узлах,
а дерево $$F^y$$ — толстое дерево
ранга $$i$$, полученное из поддерева с корнем в узле $$y$$
удалением поддеревьев $$F^1$$ и $$F^2$$.Если узел $$y$$ не является корнем дерева $$F$$, то
удаляем из дерева $$F$$
поддерево $$F^y$$. Из трех толстых деревьев $$(F, F^1, F^2$$ )
ранга $$i$$ образуем одно дерево ранга $$i + 1$$, чей
корень $$z$$ является узлом с наименьшим ключом среди корней деревьев $$F, F^1, F^2$$. Вставляем в дерево $$F$$ вновь полученное
толстое дерево с корнем в узле $$z$$ вместо поддерева с корнем в
узле $$y$$. Если узел $$z$$ оказывается нарушенным,
инкрементируем $$d_{i+1}$$.
Значение $$i$$ -го разряда делаем нулевым.
Если узел $$y$$ — корень дерева $$F$$, то удаляем
дерево $$F$$ из кучи. Из трех толстых деревьев $$(F, F^1, F^2)$$
ранга $$i$$ образуем одно дерево ранга $$i$$, чей
корень $$z$$ является узлом
с наименьшим ключом среди ключей корней деревьев $$F, F^1, F^2$$.
Вставляем вновь полученное толстое дерево с корнем в узле $$z$$
в кучу. Значение $$i$$ -го разряда делаем нулевым.
Если ранг $$y$$ больше, чем $$i + 1$$, то, по условию
регулярности счетчика нарушений, узел $$y$$ должен иметь хотя бы одного
сына $$w$$ ранга $$i + 1$$, который не является $$(i +
1)$$ -ранговым нарушением, и два $$i$$ -ранговых сына $$w$$ должны быть
также ненарушенными.
Тогда заменяем два нарушенных $$i$$ -ранговых сына
узла $$y$$ на два хороших $$i$$ -ранговых сына
узла $$w$$. Тем самым мы свели задачу к случаю 1.
Можно доказать, что рассматриваемая операция не испортит регулярности
счетчика.
Инкрементирование i-го разряда счетчика
нарушений $$({\rm IncCount Violation(i,p)}).$$
Используя описанную выше операцию фиксации, можно
осуществить инкрементирование $$i$$ -го разряда счетчика нарушений
следующими операторами:
$$\formula{
{\rm FixCountViolation} (i);\\
{\rm FixCountViolation} ({\rm CountViolation} [i]\t{\^{}}.
{\rm ForwardPointer});\\
\mbox{}\q {\rm InsertViolation}(i, {\rm pNode});\\
{\rm CountViolation}[i].{\rm Value}:= {\rm CountViolation}[i].{\rm Value} +
1;\\
{\rm FixCountViolation} (i);\\
{\rm FixCountViolation}\ ({\rm CountViolation} [i]\t{\^{}}.
{\rm ForwardPointer});
}$$
Трудоемкость операции $$O(1)$$.
Удаление нарушения из кучи.
Заметим, что удаление нарушения из кучи подразумевает наличие в куче этого нарушения; пусть это нарушение
ранга $$i$$. Тогда значение $$i$$ -го разряда для счетчика
нарушений не равно нулю. Следовательно, уменьшение этого значения на единицу не
испортит регулярности и не потребует обновления каких-либо указателей.
Необходимо лишь уменьшить на единицу значение переменной $${\rm CountViolation} [i].{\rm Value}$$ и обработать указатели $${\rm FirstViolation}$$ и $${\rm SecondViolation}$$.
Очевидно, что трудоемкость этой операции $$O(1)$$.
Нахождение узла с минимальным
значением ключа среди всех нарушений.
Для реализации этой функции предлагается перебрать все
нарушения до максимального ранга и найти среди них узел с минимальным
весом. Трудоемкость данной операции $$O(\log n)$$.
Основные операции
Операция make-heap
заключается в инициализации счетчиков. Трудоемкость $$O(1)$$.
Операция FindMin возвращает указатель
на минимальный элемент. Трудоемкость $$O(1)$$.
Операция Insert(key).
Чтобы выполнить эту операцию, делаем новый элемент отдельным
деревом и выполняем процедуру вставки нового элемента ранга $$0$$ в
корневой счетчик. После этого, если необходимо, корректируем значение указателя на
минимальный элемент.
Операция уменьшения ключа
DecreaseKey.
Чтобы выполнить эту операцию, поступим следующим образом.
Пусть $$x$$ — узел, на который указывает указатель $$p$$.
Вычитаем $$\Dl$$ из ключа узла $$x$$. Если новый
ключ $$x$$ меньше минимального ключа кучи $$H$$,
обмениваем ключ элемента $$p$$ с ключом минимального элемента. Новых
нарушений операция не создаст. Пусть $$r$$ — ранг $$x$$.
Если $$x$$ — нарушаемый узел, добавляем $$x$$ как
новое $$r$$ -ранговое нарушение
инкрементированием $$r$$ -й цифры $$d_r$$ счетчика нарушений.
Трудоемкость $$O(1)$$.
Операция DeleteMin
выполняется следующим образом. Удаляем поддерево с корнем в минимальном узле из леса.
Минимальность этого элемента гарантирует нам, что среди его детей
нарушений порядка кучи не было. То есть нет необходимости работать со
счетчиком нарушений. Затем вставляем в кучу все деревья с корнями,
расположенными в детях удаляемого узла. Очевидно, что новый минимальный
ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск
нового минимального элемента среди корней деревьев и нарушенных узлов.
Если минимальный элемент оказался в нарушенном узле, то обмениваем его
с элементом, хранимым в корне этого дерева, корректируя корневой счетчик,
если это необходимо. После замены новый минимум — в корне дерева леса.
Этот корень будет новым минимальным узлом. Трудоемкость операции
равна $$O(\log n)$$.
Операция удаления элемента.
Выполняется с помощью $${\rm DecreaseKey}$$ и затем $${\rm DeleteMin}$$. Трудоемкость
операции $$O(\log n)$$.
Операция Meld(h1, h2).
Выполняется следующим образом. Первый
шаг — фиксируются все нарушения в куче с меньшим максимальным рангом
(разрывая связь произвольно). Не уменьшая общности, считаем, что эта
куча — $$h2$$. Пройти по счетчику нарушений $$h2$$ от
младшей цифры к старшей, пропуская цифры со значением $$0$$. Для $$i$$ -й
цифры $$d_i \ne 0$$ делаем операцию фиксирования на каждой цифре,
показываемой прямым указателем $$d_i$$, если эта цифра имеет значение 2. Затем,
если $$d_i = 2$$, фиксируем $$d_i$$. Если $$d_i = 1$$,
преобразуем это $$i$$ -ранговое нарушение в $$(i +
1)$$ -ранговое нарушение, как при фиксировании, используя $$i$$ -рангового брата
нарушенного узла вместо (несуществующего) другого $$i$$ -рангового
нарушения.
Как только $$h2$$ не будет содержать каких-либо нарушений, нужно
вставить корни из корневого счетчика $$h2$$ в корневой
счетчик $$h1$$ инкрементированием соответствующих цифр. Если
минимальный узел $$h2$$ содержит меньший ключ, чем минимальный
узел $$h1$$, следует установить
новым минимальным узлом $$h1$$ минимальный узел $$h2$$. Затем
нужно вернуть модифицированную кучу $$h1$$ в качестве результата $${\rm
Meld}$$. Трудоемкость операции равна $$O(\log n)$$.
Операция DeleteViolation. Для освобождения кучи от нарушений
достаточно выполнить операторы
$$\formula{
\t for\ i:= 0\ \t{to}\ h2\t{\^{}}.{\rm
MaxRank}\ \t do\\
\t if\ ({\rm CountViolation}[i].{\rm
Value} = 2)\
\t then\ {\rm FixCountViolation}(i);\\
\t for\ i:= 0\ \t{to}\ h2\t{\^{}}.{\rm
MaxRank}\ \t do\
\t if\ ({\rm CountViolation}[i].{\rm
Value} = 1)\ \t then \\
\{{\rm IncCountViolation}(i, {\rm SearchBrother}
({\rm CountViolation}[i].{\\rm FirstViolation}));\\
{\rm FixCountViolation}(i)\};
}$$
Основываясь на описанной выше реализации толстой кучи, получаем следующий
результат. В толстых кучах операции $${\rm FindMin}, {\rm
Insert}$$ и $${\rm DecreaseKey}$$ выполняются за
время $$O(1)$$,
а $${\rm Delete}, {\rm DeleteMin}$$ и $${\rm Meld}$$ — за
время $$O(\log n)$$.
Замечание.
Существует альтернативное представление избыточных
счетчиков. Вместо одной записи на цифру можно использовать одну запись на
блок одинаковых цифр. Инкрементирование любой цифры можно выполнить за
время $$O(1)$$, используя это альтернативное представление.
Преимущество такого представления — возможность расширить счетчик на произвольное
число одинаковых цифр за постоянное время.
Г.Бродал описывает кучевидную структуру, которая теоретически лучше, чем
толстые кучи, так как их временная оценка
для $${\rm Meld}$$ — $$O(1)$$ в худшем случае. Структура
Бродала, однако, намного сложнее толстых куч.
Сводные сведения о трудоемкости операций с приоритетными
очередями
1.Трудоемкость операций над различными реализациями приоритетной
очереди в худшем случае
| Операции |
$$d$$ -куча |
Левосторонняя куча |
Ленивая левосторонняя куча |
Самоорганизующаяся куча |
Биномиальная очередь |
Ленивая биномиальная очередь |
Фибоначчиева куча |
Слаборастущая куча (run-relaxed) |
Куча Бродала |
|---|
| ВСТАВИТЬ |
$$O(\log_d n)$$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(n) $$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(1) $$ |
| МИН |
$$O(1)$$ |
$$O(1)$$ |
$$O(F)^\ast$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
| УДАЛИТЬ МИН |
$$O(d \log_d n)$$ |
$$O(\log n)$$ |
$$O(F)^\ast$$ |
$$O(n)$$ |
$$O(\log n)$$ |
$$O(n)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
| УДАЛИТЬ |
$$O(d \log_d n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
| УМЕНЬШИТЬ КЛЮЧ |
$$O(\log_d n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$\ldots$$ |
$$O(1)$$ |
$$O(1)$$ |
| СЛИТЬ |
$$-$$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
|
$$O(\log n)$$ |
$$O(1)$$ |
| ОБРАЗОВАТЬ ОЧЕРЕДЬ |
$$O(n)$$ |
$$O(n)$$ |
$$O(n)$$ |
$$\ldots$$ |
$$O(n)$$ |
|
|
$$O(1)$$ |
$$O(1)$$ |
$$^\ast\, F = k \max \{1,\log (n/(k + 1))\}$$
2. Амортизационная трудоемкость выполнения операций
| Операции |
$$d$$ -куча |
Левосторонняя куча |
Ленивая левосторонняя куча |
Самоорганизующаяся куча |
Биномиальная очередь |
Ленивая биномиальная очередь |
Фибоначчиева куча |
Слаборастущая куча (run-relaxed) |
Куча Бродала |
|---|
| ВСТАВИТЬ |
$$O(\log_d n)$$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(1) $$ |
$$O(1) $$ |
| МИН |
$$O(1)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
| УДАЛИТЬ МИН |
$$O(d \log_d n)$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
| УДАЛИТЬ |
$$O(d \log_d n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
| УМЕНЬШИТЬ КЛЮЧ |
$$O(\log_d n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$\ldots$$ |
$$O(\log n)$$ |
$$\ldots$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
| СЛИТЬ |
$$-$$ |
$$O(\log n)$$ |
$$O(1) $$ |
$$O(\log n)$$ |
$$O(\log n)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
$$O(\log n)$$ |
| ОБРАЗОВАТЬ ОЧЕРЕДЬ |
$$O(n)$$ |
$$O(n)$$ |
$$O(n)$$ |
$$\ldots$$ |
$$O(n)$$ |
|
$$O(1)$$ |
$$O(1)$$ |
$$O(1)$$ |
