1632
правки
Изменения
м
'''Свойства толстых деревьев:''' <br>*В толстом дереве ранга <tex>k</tex> ровно <tex>3^k</tex> узлов. <br>*Для любого натурального числа <tex>n</tex> существует лес из толстых деревьев, в котором ровно <tex>n</tex> узлов. Такой лес можно построить, включив в него столько деревьев ранга <tex>i</tex>, каково значение <tex>i</tex>-го разряда представления числа <tex>n</tex> в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.*Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log({n)})</tex> деревьев.
=Толстые кучи=Здесь и далее ''Толстая куча на избыточном счетчике'' будет заменено на более лаконичное ''Толстая куча''.
* '''struct''' Node '''int''' key <texspan style="color:#008000">Key< //tex> {{---}} ключ элемента, приписанного узлу дерева</span>* '''Node''' parent <texspan style="color:#008000">Parent< //tex> {{---}} указатель на родителяузла</span>* '''Node''' left <texspan style="color:#008000">Lest< //tex> {{---}} указатель на ближайшего левого братаузла</span>* '''Node''' right <texspan style="color:#008000">Right< //tex> {{---}} указатель на ближайшего правого братаузла</span>* '''Node''' lChild <texspan style="color:#008000">LChild< //tex> {{---}} указатель на самого левого сына*<tex>Rank</texspan> {{---}} ранг узла. "Братья" связаны в двусвязный список при помощи указателей '''int''' rank <tex>Left</tex> и <tex>Right</tex>. У самого левого (правого) span style="братаcolor:#008000" в этом списке указатель <tex>Left< /tex> (<tex>Right</tex>) равен <tex>NULLранг узла</texspan>.
<tex>FatHeap = (RootCount, CountViolation, Minpointer, MaxRank)</tex>, где:
<tex>CountViolation</tex> {{---}} массив, соответствующий '''счетчику нарушений'''==Избыточное представление чисел==
Избыточным Пусть <tex>L(i)</tex> — номер разряда, отличного от <tex>b-1</tex> и ближайшего слева от <tex>i</tex>-арным представлением числа го разряда в регулярном <tex>xb</tex> будем называть последовательность -арном избыточном представлении <tex>d = d_n, d_\ldots, d_0</tex>.<br>'''Прямой указатель''' <tex>L'(i)</tex> определим следующим образом: *<tex>L'(i) = L(i)</tex> , если <tex>d_i \in \{nb-1, b-2\}</tex> и <tex>d(L(i))=b</tex>;*<tex>L'(i)</tex> — произвольное число <tex>>i</tex>, ... d_0если <tex>d_i \in \{b-1, b-2\}</tex> и <tex>d(L(i))<b-1</tex>; *<tex>L'(i)</tex> — не определено, такую чтоесли <tex dpi = "150">x = d \notin \{b-1, b-2 \sum}</tex> .}} ===Фиксация цифры===Фиксацией цифры <tex>b</tex>, стоящей в <tex>i</tex>-м разряде представления <tex>d</tex>, назовем операцию <tex>\limits^mathrm{fix(i)}</tex>, заключающуюся в обнулении цифры <tex>d_i</tex> и инкрементировании цифры <tex> d_{i+1} </tex>, при этом если <tex>i=n</tex> , то полагаем <tex>d_{i+1}_= 1</tex>. При каждом выполнении операции фиксации будем обновлять значение <tex>L'(i)</tex>. Очевидно, при <tex>b>2</tex> операцию <tex>\mathrm{fix(i)}</tex> можно выполнить следующим образом: '''void''' fix('''int''' i): '''if''' d[i] == b d[i ] = 0} d[i + 1]++ '''if''' d[i + 1] == b - 1: L'[i] = L'[i + 1] '''else''' L'[i] = i + 1 ===Инкремент===Операцию <tex>\mathrm{d_iinc(i)}}{</tex> инкрементирования <tex>i</tex>-й цифры избыточного представления <tex>d</tex> можно выполнить так: '''void''' inc('''int''' i): fix(i) '''if''' (d[i] == b^- 1) '''or''' (d[i}] == b - 2) fix(L'[i]) d[i]++ fix(i) ===Декремент=== Эта схема может быть расширена для выполнения за константное время декрементирования произвольной цифры добавлением дополнительного цифрового значения <tex>b+1</tex>.
где Представление приоритетной очереди основано на использовании так называемых '''избыточных счетчиков''', позволяющих за время <tex> d_i \in \{0, O(1, ..., b\} )</tex>инкрементировать любой разряд. Заметим, <tex> i \in \{0что использованные здесь счетчики — лишь '''один из способов реализации''' толстых куч. На самом деле, для их реализации подойдет '''произвольный d-арный''' счетчик, 1при условии, что трудоемкость инкрементирования любого его разряда является константной..., n\} </tex>}}
* <tex>DecreaseKey</tex> {{---}} <tex>O(1)</tex>===decreaseKey===
* <tex>DeleteMin</tex> {{---}} <tex>O(\log(n))</tex>===deleteMin===
* <tex>Delete</tex> {{---}} <tex>O(\log(n))</tex>
выполняем <tex>DecreaseKey</tex> а затем <tex>DeleteMin</tex>
* <tex>Meld(h1, h2)</tex> {{---}} <tex>O(\log(n))</tex>
Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — <tex>р2</tex> . Пройти по счетчику нарушений <tex>p2</tex> от младшей цифры к старшей, пропуская цифры со значением <tex>0</tex> . Для <tex>i</tex>-й цифры <tex>d_i != 0</tex> делаем операцию фиксирования на каждой цифре, показываемой прямым указателем <tex>d_i</tex> , если эта цифра имеет значение 2. Затем, если <tex>d_i = 2</tex> , фиксируем <tex>d_i</tex> . Если <tex>d_i = 1</tex> , преобразуем это <tex>i</tex>-ранговое нарушение в <tex>(i+1)</tex>-ранговое нарушение, как при фиксировании, используя <tex>i</tex>-рангового брата нарушенного узла вместо (несуществующего) другого <tex>i</tex> -рангового нарушения.
Как только <tex>h2</tex> не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика <tex>h2</tex> в корневой счетчик <tex>h1</tex> инкрементированием соответствующих цифр. Если минимальный узел <tex>h2</tex> содержит меньший ключ, чем минимальный узел <tex>h1</tex> , следует установить новым минимальным узлом <tex>h1</tex> минимальный узел <tex>h2</tex> . Затем нужно вернуть модифицированную кучу <tex>h1</tex> в качестве результата <tex>Meld</tex> .
* <tex>DeleteViolation</tex>
для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
<code>
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);
</code>
rollbackEdits.php mass rollback
==Толстое дерево==
{{Определение
|id=def1.
|neat = 1
|definition=
Определяем '''толстое дерево''' (англ. ''Thick tree'') <tex>F_k</tex> ранга <tex>k</tex>, <tex>~(k = 0, 1, 2, \dots ldots )</tex> следующим образом:
*Толстое дерево <tex>F_0</tex> ранга ноль состоит из единственного узла. <br>
*Толстое дерево <tex>F_k</tex> ранга <tex>k</tex>, для <tex>k = 1, 2, 3,\dots ldots </tex>, состоит из трех деревьев <tex>F_{k-1}</tex> ранга <tex>k-1</tex>, связанных тактаких, что корни двух из них являются самыми левыми потомками корня третьего.}}[[Файл:FatHeap.png |400px|thumb|center|Пример толстых деревьев <tex>F_0, F_1, F_2, F_3</tex>]] {{Определение|id=def3 |neat =|definition='''Ранг узла ''' <tex>x</tex> в толстом дереве определяется как ранг толстого поддерева с корнем в узле <tex>x</tex>.
}}
===Свойства толстых деревьев===
{{Утверждение|id=proposal1. |author=|about=|statement=В толстом дереве ранга <tex>k<//[[Файл:ThickTreeExample.gif Пример толстых деревьев tex> ровно <tex>F_0, F_1, F_2, F_33^k</tex>]]узлов.|proof=}}{{Определение|id=thin_forest_def|definition='''Толстый лес''' (англ. ''Thick forest'') {{---}} это набор толстых деревьев, ранги которых не обязательно попарно различны.}}
{{Утверждение|id=proposal1. |author= Свойства Толстых |about=|statement=Для любого натурального числа <tex>n</tex> существует лес из толстых деревьев , в котором ровно <tex>n</tex> узлов. |proof==Действительно, такой лес можно построить, включив в него столько деревьев ранга <tex>i</tex>, каково значение <tex>i</tex>-го разряда представления числа <tex>n</tex> в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.}}
{{Утверждение
|about=
|statement=
|proof=
}}
==Толстые кучи==
{{Определение
|id=def2
|neat =
|definition=
'''лесЛес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.
}}
{{Определение
|neat =
|definition=
'''Узел''' (англ. ''Node'') в '''нагруженном лесе''' назовем '''неправильным''', если его ключ меньше ключа его родителя.
}}
{{Определение
'''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</tex>.
}}
{{Определение
|id=def5
|neat =
|definition=
'''Толстая куча''' (англ. ''Thick heap, Fat heap'') — это '''почти кучеобразный''' '''нагруженный лес'''.
}}
==Представление толстой кучи= Структура узла ===
Каждый узел толстой кучи будем представлять записью со следующими полями:
"Братья" (узлы корневых деревьев, а также сыновья каждого узла) объединены в двусвязный список при помощи указателей <tex>left</tex> и <tex>right</[[Файл:ThickTreeExampletex>.gif Пример толстых деревьев У самого левого (правого) "брата" в этом списке указатель <tex>left</tex> (<tex>right</tex>) равен <tex>F_0, F_1, F_2, F_3NULL</tex>]] =Вспомогательные структуры=Нам понадобятся понятия '''корневого счетчика''' и '''счетчика нарушений'''.
===Структура кучи===
Толстую кучу будем представлять записью следующего вида:
'''struct''' FatHeap '''int[]''' rootCount <texspan style="color:#008000">RootCount // массив, соответствующий корневому счетчику</texspan> '''int[]''' countViolation <span style="color:#008000"> {{---}} // массив, соответствующий счетчику нарушений</span> '''Node''' minPointer <span style="color:#008000"> // указатель на элемент кучи с минимальным ключом</span> '''корневому счетчикуint'''maxRank <span style="color:#008000"> // наибольший ранг среди рангов деревьев, присутствующих в куче</span>[[Файл:FatHeapExample.png |400px|thumb|center|Представление леса списком]]
{{Определение|id=|neat = |definition='''Избыточным''' <tex>b</tex>-арным представлением числа <tex>x</tex> будем называть последовательность <tex>MinPointerd = d_n, d_{n-1}, \ldots, d_0</tex> , такую что<tex dpi = "120">x = {\sum\limits^{n}_{i = 0} {---d_i}}{b^i} указатель на элемент кучи с '''минимальным ключом'''</tex>
где <tex>MaxRankd_i \in \{0, 1, \ldots, b\} </tex> , <tex> i \in \{{---0, 1, \ldots, n\} </tex>}} '''наибольший ранг''' среди рангов деревьев, присутствующих в куче
{{Определение|id=|neat =Избыточное |definition=Назовем <tex>b</tex>-арное избыточное представление чисел==числа '''регулярным''', если в нем между любыми двумя цифрами, равными <tex>b</tex> , найдется цифра, отличная от <tex>b-1</tex>.}}
{{Определение
|neat =
|definition=
==Корневой счетчик==
Значение его <tex>i</tex>-го разряда равно количеству деревьев ранга <tex>i</tex>, присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга <tex>i</tex> содержит ровно <tex>3^i</tex> узлов.
Заметим, что состояние избыточного корневого представления определяется неоднозначно. Очевидно, что для любой толстой кучи, состоящей из <tex>n</tex> элементов, существует регулярное избыточное представление корневого счетчика.
Списочный элемент, приписанный <tex>i</tex>-му разряду избыточного корневого представления, — это указатель на список деревьев ранга <tex>i</tex>, присутствующих в куче, образованный посредством указателей <tex>Rightright</tex> корневых узлов связываемых деревьев.
{{Утверждение
}}
'''корневой Корневой счетчик''' представляем расширяющимся массивом <tex>RootCount\mathtt{rootCount}</tex> , каждый элемент которого — запись с тремя полями:*<tex>RootCount\mathtt{rootCount[i].Value}</tex> {{---}} <tex>i</tex>-й разряд равный количеству деревьев ранга <tex>i</tex>.*<tex>RootCount\mathtt{rootCount[i].ForvardPointerforwardPointer}</tex> {{---}} прямой указатель <tex>i</tex>-го разряда.*<tex>RootCount\mathtt{rootCount[i].ListPointerlistPointer}</tex> {{---}} указатель на список деревьев ранга <tex>i</tex>, присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя <tex>Right</tex> корневых узлов связываемых деревьев. Если в куче нет деревьев ранга <tex>i</tex> , то указатель <tex>ListPointer\mathtt{listPointer}</tex> равен <tex>NULL</tex>. ''Заметим, что если значение равно нулю, то нам неважно значение указателя'' <tex>RootCount\mathtt{rootCount[i].ListPointerlistPointer}</tex>.
===Инициализация===
Чтобы время инициализации счетчиков было <tex>O(1)</tex>, используем '''поразрядную''' их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную <tex>MaxRank\mathtt{maxRank}</tex>, которая показывает нам, какая часть массивов счетчиков используется в данный момент.
При начальной инициализации необходимо установить счетчики в состояние, которое отвечает '''пустой куче'''. Очевидно, что в пустой куче не может быть никаких нарушений.
===Обновление прямого указателя===
Обновление прямого указателя <tex>i</tex>-го разряда корневого счетчика заключается в выполнении следующего псевдокода:<code> '''void''' updateForwardPionter('''int''' i): '''if (RootCount''' rootCount[i+1].Value==3-1) RootCountrootCount[i].ForwardPointer :forwardPointer = RootCountrootCount[i+1].ForwardPointer;forwardPointer '''else''' RootCountrootCount[i].ForwardPointer :forwardPointer = i + 1;</code>
===Корректировка при вставке ===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при вставке в кучу нового дерева ранга <tex>i</tex> ~(<tex>InsertTree\mathrm{insertTree(i,p)})</tex>). Эта процедура вставляет новое дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) в списочную часть <tex>i</tex> -го разряда корневого счетчика <tex>RootCount\mathtt{rootCount}</tex> выглядит так: '''void''' insertTree('''int''' i, '''Node''' p):<code> p1 := RootCountrootCount[i].ListPointer;listPointer '''if(RootCount''' rootCount[i].Value != <tex> \ne </tex> 0) p.Right right = p1; '''else''' p.Right right = NULL; p.Left :left = NULL; RootCount rootCount[i].ListPointer :listPointer = p;</code>
===Корректировка при удалении===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при удалении из кучи дерева ранга <tex>i</tex> ~(<tex>DeleteTree\mathrm{deleteTree(i,p)})</tex>). Эта процедура удаляет дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) из списочной части <tex>i</tex>-го разряда корневого счетчика <tex>RootCount\mathtt{rootCount}</tex> . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода: '''void''' deleteTree('''int''' i, '''Node''' p):<code> p1 := RootCountrootCount[i].ListPointer;listPointer '''if(''' p1 == p) RootCountrootCount[i].ListPointer :listPointer = p.Right;right j:= 1; '''while''' (j<=RootCounttex> \leqslant </tex> rootCount[i].Value) '''and ''' (p1.Right != right <tex> \ne </tex> p) do: j++ p1 = p1.right p1.Right right = p.Right;</code>right
===Связывание трех деревьев в одно===
'''Связывание''' <tex>(Fastening \mathrm{fastening (p1, p2, p3))}</tex> трех толстых деревьев ранга <tex>i</tex> в одно толстое дерево ранга <tex>i+1</tex>. Эта функция принимает три указателя <tex>(p1, p2 ,p3)</tex> на три разных толстых дерева одного и того же ранга <tex>i</tex> и возвращает указатель на вновь сформированное дерево ранга <tex>i+1</tex> .
Процедура заключается в выполнении следующего псевдокода:
'''Node''' fastening('''Node''' p1, '''Node''' p2, '''Node''' p3):<code> '''if''' (p1.Keykey <tex> \leqslant <=/tex> p2.Keykey) '''and ''' (p1.Key<=tex> \leqslant </tex> p3.Keykey) MinP :minP = p1; p1 := p2; p2 := p3; '''if''' (p2.Keykey <tex> \leqslant <=/tex> p1.Keykey) '''and''' (p2.Keykey <tex> \leqslant <=/tex> p3.Keykey) MinP :minP = p2; p1 := p1; p2 := p3; '''if''' (p3.Keykey <tex> \leqslant <=/tex> p1.Keykey) '''and''' (p3.Keykey <tex> \leqslant <=/tex> p2.Keykey) MinP :minP = p3; p1 := p1; p2 := p2; p1.Right :right = p2; p1.Left :left = NULL; p1.Parent :parent = MinP;minP p2.Right :right =MinPminP.LChild;lChild p2.Left :left =p1; p2.Parent :parent = MinP;minP '''if(MinP''' minP.LChild != lChild <tex> \ne </tex> NULL) MinPminP.LChildlChild.Left left = p2; MinP minP.LChild :lChild = p1; MinP minP.Rank :rank = MinPminP.Rankrank +1; MinP minP.Right :right = NULL; MinP minP.Left :left = NULL; Fastening := MinP; </code> '''return''' minP
===Значение ключа элемента по указателю===
Функция <tex>GetKey\mathrm{getKey(p)}</tex> по указателю p на элемент определяет значение его ключа: <font color=green>//под <tex>\infty</tex> нужно понимать нейтральный относительно минимума элемент.<code/font> '''int''' getKey('''Node''' p): '''if(''' p == NULL) Min :min = <tex>\infty</tex>; '''else''' Min :min = p.key; GetKey := Min; </code> '''return''' min
===Узел с минимальным ключом===
Функция <tex>MinKeyNodeRoot\mathrm{minKeyNodeRoot(p)}</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:<code> p1:='''Node''' minKeyNodeRoot('''Node''' p; MinP ):= p1; while ( p1 != NULL) do if(p1.Key < MinP.Key)p MinP : minP = p1; p1 := '''while''' p1.Right; MinKeyNodeRoot := MinP;</code> ===Операция фиксации <tex>rmFixRootCount(i)\ne </tex>===NULLОперация фиксации <tex>i</tex>-го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга <tex>i</tex>, состоящий ровно из трех деревьев. При выполнении этой операции значение в <tex>i</tex>-м разряде — должно стать равным нулю, а значение в <tex>i</tex>-м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга <tex>i</tex>, а количество деревьев ранга <tex>i+1</tex> должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга <tex>i</tex> , связать их в дерево ранга <tex>i+1</tex> и вставить вновь полученное дерево в кучу.Следует учесть, что ранг нового дерева может стать больше, чем <tex>MaxRank</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>MaxRank</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда '''if''' p1. key <code> if(MaxRank = i) maxRank := i + 1; RootCount[i+1].Value := 0; CountViolation[i+1]minP.Value := 0; else UpdateForwardPointer(i+1);key RootCount[i].Value : minP = 0; p1 := RootCount[i].ListPointer; p2 := p1.Right; p3 := p2.Right; p := Fastening(p1, p2, p3); RootCount[i].ListPointer := NULL; InsertTree(i+1, p);right RootCount[i+1].Value := RootCount[i+1].Value + 1; </code> ===Инкрементирование i-го разряда корневого счетчика <tex>rm IncRootCount(i,p)</tex>===Здесь мы должны учесть работу со списочной частью и обновить прямые указатели. '''return''' minP
===Операция фиксации ===Операция фиксации <tex>\mathrm{rmFixRootCount(i)}</tex> для <tex>i</tex>-го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга <tex>i</tex>, состоящий ровно из трех деревьев. При выполнении этой операции значение в <tex>i</tex>-м разряде — должно стать равным нулю, а значение в <tex>i</tex>-м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга <codetex>i</tex>, а количество деревьев ранга <tex>i+1</tex> должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга <tex>i</tex> , связать их в дерево ранга <tex>i+1</tex> и вставить вновь полученное дерево в кучу.Следует учесть, что ранг нового дерева может стать больше, чем <tex>\mathtt{maxRank}</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>\mathtt{maxRank}</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда. '''void''' rmFixRootCount('''int''' i) '''if(RootCount''' maxRank == i maxRank = i + 1 rootCount[i+ 1].Value = 1) or (RootCount0 countViolation[i+ 1].Value = 2)0 '''else''' ifupdateForwardPointer(RootCount[Rootcounti + 1) rootCount[i].ForwardPointer)Value = 0 if(RootCount p1 = rootCount[i].Value listPointer p2 = p1.right p3 = p2.right p = 3fastening(p1, p2, p3) FixRootCount( rootCount[i);].listPointer = NULL InsertTree insertTree(i+ 1,p); RootCount rootCount[i+ 1].Value := RootCountrootCount[i+ 1].Value + 1; UpdateForwardPointer(i); if(rootcount[i].Value = 3) FixRootCount(i);</code>
===удаление дерева из кучиИнкрементирование i-го разряда корневого счетчика===Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг . Тогда значение По сравнению с описанным алгоритмом инкрементирования <tex>i</tex>-го разряда избыточного корневого представления не равно нулюздесь мы должны учесть работу со списочной частью и обновить прямые указатели. '''void''' rmIncRootCount('''int''' i, '''Node''' p) '''if''' (rootCount[i]. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателейValue == 1) '''or''' (rootCount[i].Value == 2) '''if''' rootCount[rootCount[i].forwardPointer]. Необходимо лишь соответствующим образом обработать списочную частьValue == 3 fixRootCount(rootCount[i].forwardPointer);<code> '''if''' rootCount[i].Value == 3 fixRootCount(i) DeleteTree insertTree(i,p); RootCount rootCount[i].Value := RootCountrootCount[i].Value -+ 1;</code> updateForwardPointer(i) '''if''' rootCount[i].Value == 3 fixRootCount(i)
===Нахождение Удаление дерева с минимальным ключом из кучи===Процедура удаления дерева из кучи подразумевает наличие в корне (куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>MinKeyi</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть. '''void''' delete('''int''' i, '''Node''' p): deleteTree(i, p) rootCount[i].Value ===rootCount[i].Value - 1
===Нахождение дерева с минимальным ключом в корне <tex>\mathrm{minKey()}<code/tex>=== MinP :'''Node''' minKey() minP = NULL; '''for(''' i := 0 to MaxRank) domaxRank: p1:=MinKeyNodeRootminKeyNodeRoot(RootCountrootCount[i].ListPointerlistPointer); '''if(GetKey''' getKey(p1)<GetKeygetKey(MinP)minP): MinP : minP = p1; MinKey := MinP;</code> '''return''' minP
==Счетчик нарушений==
'''Счетчик нарушений''' состоит из расширенного избыточного двоичного представления и набора списочных элементов.
'''Счетчик нарушений''' представлен [[Саморасширяющийся массив|Саморасширяющимся саморасширяющимся массивом]], элементы которого состоят из четырех полей:*<tex>CountViolation\mathtt{countViolation[i].Value}</tex> {{---}} количество неправильных узлов ранга <tex>i</tex> в куче.*<tex>CountViolation\mathtt{countViolation[i].ForvardPointerforvardPointer}</tex> {{---}} прямой указатель <tex>i</tex>-го разряда*<tex>CountViolation\mathtt{countViolation[i].FirstViolationfirstViolation}</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>*<tex>CountViolation\mathtt{countViolation[i].SecondViolationsecondViolation}</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>
{{Утверждение
}}
Для '''инициализации''' нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга <tex>MaxRank \mathtt{maxRank + 1}</tex>. Это первый момент появления в куче узла ранга <tex>MaxRank \mathtt{maxRank + 1}</tex>. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного <tex>MaxRank \mathtt{maxRank + 1}</tex>, соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
==Основные операции==* Рассмотрим операции, которые можно производить с толстой кучей. Время работы основных операций указано в таблице:{| class="wikitable" style="width:10cm" border=1|+|-align="center" bgcolor=#EEEEFF! Операция || Время работы |-align="center" bgcolor=#FFFFFF|<tex>\mathrm{makeHeap}</tex>MakeHeap||<tex>O(1)</tex> |-align="center" bgcolor=#FFFFFF|<tex>\mathrm{{---}findMin}</tex>||<tex>O(1)</tex>заключается в инициализации счетчиков. |-align="center" bgcolor=#FFFFFF* ||<tex>FindMin\mathrm{insert(key)}</tex>||<tex>O(1)</tex> |-align="center" bgcolor=#FFFFFF|<tex>\mathrm{{---}decreaseKey}</tex>||<tex>O(1)</tex>возвращает указатель на минимальный элемент. |-align="center" bgcolor=#FFFFFF* |<tex>Insert\mathrm{deleteMin}</tex>||<tex>O(\log(keyn))</tex> |-align="center" bgcolor=#FFFFFF|<tex>\mathrm{delete}</tex>||<tex>O(\log(n))</tex>|-align="center" bgcolor=#FFFFFF|<tex>\mathrm{---}meld(h1, h2)} </tex>||<tex>O(1\log(n))</tex>|} ===makeHeap===Заключается в инициализации счетчиков. ===findMin===Возвращает указатель на минимальный элемент. ===insert(key)===
Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга <tex>0</tex> в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
Чтобы выполнить эту операцию, поступим следующим образом. Пусть <tex>x</tex> — узел, на который указывает указатель <tex>p</tex> . Вычитаем <tex>\delta</tex> из ключа узла <tex>x</tex> . Если новый ключ <tex>x</tex> меньше минимального ключа кучи <tex>H</tex>, обмениваем ключ элемента <tex>p</tex> с ключом минимального элемента. Новых нарушений операция не создаст. Пусть <tex>r</tex> — ранг <tex>x</tex> . Если <tex>x</tex> — нарушаемый узел, добавляем <tex>x</tex> как новое <tex>r</tex>-ранговое нарушение инкрементированием <tex>r</tex>-й цифры <tex>d_r</tex> счетчика нарушений.
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
===delete===
Выполняем <tex>\mathrm{decreaseKey}</tex> а затем <tex>\mathrm{deleteMin}</tex>.
===meld(h1, h2)===
Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — <tex>р2</tex> . Пройти по счетчику нарушений <tex>p2</tex> от младшей цифры к старшей, пропуская цифры со значением <tex>0</tex> . Для <tex>i</tex>-й цифры <tex>d_i != 0</tex> делаем операцию фиксирования на каждой цифре, показываемой прямым указателем <tex>d_i</tex> , если эта цифра имеет значение <tex>2</tex>. Затем, если <tex>d_i = 2</tex> , фиксируем <tex>d_i</tex> . Если <tex>d_i = 1</tex> , преобразуем это <tex>i</tex>-ранговое нарушение в <tex>(i+1)</tex>-ранговое нарушение, как при фиксировании, используя <tex>i</tex>-рангового брата нарушенного узла вместо (несуществующего) другого <tex>i</tex> -рангового нарушения.
Как только <tex>h2</tex> не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика <tex>h2</tex> в корневой счетчик <tex>h1</tex> инкрементированием соответствующих цифр. Если минимальный узел <tex>h2</tex> содержит меньший ключ, чем минимальный узел <tex>h1</tex> , следует установить новым минимальным узлом <tex>h1</tex> минимальный узел <tex>h2</tex> . Затем нужно вернуть модифицированную кучу <tex>h1</tex> в качестве результата <tex>\mathrm{meld}</tex> .
===deleteViolation===
Для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
'''void''' deleteViolation('''Node''' h2):
'''for''' i = 0 '''to''' h2.maxRank
'''if''' countViolation[i].Value == 2
fixCountViolation(i)
'''for''' i = 0 to h2.maxRank
'''if''' countViolation[i].Value == 1
incCountViolation(i, searchBrother(countViolation[i].rmFirstviolation))
fixCountViolation(i)
==См. также==
* [[Тонкая куча]]
==Источникиинформации==* [http://www.intuit.ru/studies/courses/100/100/lecture/15432935?page=1 INTUIT.ru {{---}} Толстые кучи ]* [https://www.lektorium.tv/lecture/14234 CS center {{---}} Приоритетные очереди]* [http://www.cs.tau.ac.il/~haimk/papers/newthin1.pdf H.Kaplan, R.Tarjan. "Thin Heaps, Thick Heaps". — INTUIT.ru2006]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
