Изменения

==Толстое дерево= =

Определяем '''толстое дерево''' (англ. ''Thick tree'') <tex>F_k</tex> ранга <tex>k ~(k = 0, 1, 2 ~,\dots ldots )</tex> следующим образом:

*Толстое дерево <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>.

'''Свойства толстых деревьев:''' <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> деревьев.

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

 =Толстые кучи=Здесь и далее ''Толстая куча на избыточном счетчике'' будет заменено на более лаконичное ''Толстая куча''.

'''Толстая куча''' (англ. ''Thick heap, Fat heap'') — это '''почти кучеобразный''' '''нагруженный лес'''.

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

* '''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">Left< //tex> {{---}} указатель на ближайшего левого братаузла</span>* '''Node''' right <texspan style="color:#008000">Right< //tex> {{---}} указатель на ближайшего правого братаузла</span>* '''Node''' lChild <texspan style="color:#008000">LChild< //tex> {{---}} указатель на самого левого сына*<tex>Rank</texspan> {{---}} ранг узла. "Братья" (узлы корневых деревьев, а также сыновья каждого узла) объединены в двусвязный список при помощи указателей <tex>Left '''int''' rank </tex> и <tex>Right</tex>. У самого левого (правого) span style="братаcolor:#008000" в этом списке указатель <tex>Left< /tex> (<tex>Right</tex>) равен <tex>NULLранг узла</texspan>. [[Файл:FatHeapExample.png |400px|thumb|right|Представление леса списком]]

=Вспомогательные структуры=Нам понадобятся понятия '''корневого счетчика''' "Братья" (узлы корневых деревьев, а также сыновья каждого узла) объединены в двусвязный список при помощи указателей <tex>left</tex> и '''счетчика нарушений'''<tex>right</tex>. У самого левого (правого) "брата" в этом списке указатель <tex>left</tex> (<tex>right</tex>) равен <tex>NULL</tex>.

'''struct''' FatHeap '''int[]''' rootCount <texspan style="color:#008000">MaxRank // массив, соответствующий корневому счетчику</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|Представление леса списком]]

'''Избыточным''' <tex>b</tex>-арным представлением числа <tex>x</tex> будем называть последовательность <tex>d = d_n, d_{n-1}, ... \ldots, d_0</tex>, такую что<tex dpi = "150120">x = {\sum\limits^{n}_{i = 0} {d_i}}{b^i}</tex>

где <tex> d_i \in \{0, 1, ...\ldots, b\} </tex>, <tex> i \in \{0, 1, ...\ldots, n\} </tex>

Пусть <tex>L(i)</tex> — номер разряда, отличного от <tex>b-1</tex> и ближайшего слева от <tex>i</tex>-го разряда в регулярном <tex>b</tex>-арном избыточном представлении <tex>d = d_n, ... \ldots, d_0</tex>.

Определим '''Прямой указатель''' <tex>L'(i)</tex> определим следующим образом:

===фиксация Фиксация цифры===Фиксацией цифры <tex>b</tex>, стоящей в <tex>i</tex>-м разряде представления <tex>d</tex>, (Fixназовем операцию <tex>\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>Fix\mathrm{fix(i)}</tex> можно выполнить следующим образом:<code> Fix '''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</code>

===инкрементИнкремент===Инкрементирование Операцию <tex>\mathrm{inc(i)}</tex>-й цифры избыточного представления инкрементирования <tex>di</tex> -й цифры избыточного представления <tex>Inc(i)d</tex> можно выполнить так:<code> Inc '''void''' inc('''int''' i): Fix fix(i) '''if''' (d[i] == b - 1) '''or''' (d[i] == b - 2): Fix fix(L'[i]) d[i]++ Fix fix(i)</code>

===декрементДекремент===

Списочный элемент, приписанный <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].ForwardPointerforwardPointer}</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>, которая показывает нам, какая часть массивов счетчиков используется в данный момент.

<code> UpdateForwardPionter '''void''' updateForwardPionter('''int''' i): '''if''' RootCountrootCount[i + 1].Value == 3 - 1: RootCount rootCount[i].ForwardPointer forwardPointer = RootCountrootCount[i + 1].ForwardPointerforwardPointer '''else''': RootCount rootCount[i].ForwardPointer forwardPointer = i + 1</code>

Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при вставке в кучу нового дерева ранга <tex>i~(InsertTree\mathrm{insertTree(i,p)})</tex>. Эта процедура вставляет новое дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) в списочную часть <tex>i</tex>-го разряда корневого счетчика <tex>RootCount\mathtt{rootCount}</tex> выглядит так: <code> InsertTree '''void''' insertTree('''int''' i, '''Node''' p): p1 = RootCountrootCount[i].ListPointerlistPointer '''if''' RootCountrootCount[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~(DeleteTree\mathrm{deleteTree(i,p)})</tex>. Эта процедура удаляет дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) из списочной части <tex>i</tex>-го разряда корневого счетчика <tex>RootCount\mathtt{rootCount}</tex> . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода: <code> DeleteTree '''void''' deleteTree('''int''' i, '''Node''' p): p1 = RootCountrootCount[i].ListPointerlistPointer '''if''' p1 == p: RootCount rootCount[i].ListPointer listPointer = p.Rightright j = 1 '''while''' (j <tex> \le leqslant </tex> RootCountrootCount[i].Value) '''and''' (p1.Right right <tex> \ne </tex> p): j++ p1 = p1.Rightright 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> .

 <code> Fastening '''Node''' fastening('''Node''' p1, '''Node''' p2, '''Node''' p3): '''if''' (p1.Key key <tex> \le leqslant </tex> p2.Keykey) '''and''' (p1.Key <tex> \le leqslant </tex> p3.Keykey): MinP minP = p1 p1 = p2 p2 = p3 '''if''' (p2.Key key <tex> \le leqslant </tex> p1.Keykey) '''and''' (p2.Key key <tex> \le leqslant </tex> p3.Keykey): MinP minP = p2 p1 = p1 p2 = p3 '''if''' (p3.Key key <tex> \le leqslant </tex> p1.Keykey) '''and''' (p3.Key key <tex> \le leqslant </tex> p2.Keykey) MinP minP = p3 p1 = p1 p2 = p2 p1.Right right = p2 p1.Left left = NULL p1.Parent parent = MinPminP p2.Right right = MinPminP.LChildlChild p2.Left left = p1 p2.Parent parent = MinPminP '''if''' MinPminP.LChild lChild <tex> \ne </tex> NULL: MinP minP.LChildlChild.Left left = p2 MinP minP.LChild lChild = p1 MinP minP.Rank rank = MinPminP.Rank rank + 1 MinP minP.Right right = NULL MinP minP.Left left = NULL '''return''' MinP</code>minP

Функция <tex>GetKey\mathrm{getKey(p)}</tex> по указателю p на элемент определяет значение его ключа:  <font color=green>// ''под <tex>\infty</tex> нужно понимать нейтральный относительно минимума элемент.'' <code/font> GetKey '''int''' getKey('''Node''' p): '''if''' p == NULL: Min min = <tex>\infty</tex> '''else''': Min min = p.key '''return''' Min </code>min

Функция <tex>MinKeyNodeRoot\mathrm{minKeyNodeRoot(p)}</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:<code> MinKeyNodeRoot '''Node''' minKeyNodeRoot('''Node''' p): p1 = p MinP minP = p1 '''while''' p1 <tex> \ne </tex> NULL: '''if''' p1.Key key < MinPminP.Key:key MinP minP = p1 p1 = p1.Rightright '''return''' MinP</code> ===Операция фиксации <tex>rmFixRootCount(i)</tex>===Операция фиксации <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> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.minP

===Операция фиксации ===Операция фиксации <tex>\mathrm{rmFixRootCount(i)}</tex> для <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>\mathtt{maxRank}</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>\mathtt{maxRank}<code/tex>на единицу и заполнить новое поле, а также провести инициализацию нового разряда. '''void''' rmFixRootCount('''int''' i) '''if''' MaxRank maxRank == i: MaxRank maxRank = i + 1 RootCount rootCount[i + 1].Value = 0 CountViolation countViolation[i + 1].Value = 0 '''else''': UpdateForwardPointer updateForwardPointer(i + 1) RootCount rootCount[i].Value = 0 p1 = RootCountrootCount[i].ListPointerlistPointer p2 = p1.Rightright p3 = p2.Rightright p = Fasteningfastening(p1, p2, p3) RootCount rootCount[i].ListPointer listPointer = NULL InsertTree insertTree(i + 1, p) RootCount rootCount[i + 1].Value = RootCountrootCount[i + 1].Value + 1 </code>

<code> rmIncRootCount(i,p) '''if''' (RootCount[i].Value == 1) '''or''' (RootCount[i].Value == 2): '''if''' RootCount[RootCount[i].ForwardPointer].Value == 3: FixRootCount(RootCount[i].ForwardPointer); '''if''' RootCount[i].Value == 3: FixRootCount(i) InsertTree(i, p) RootCount[i].Value = RootCount[i].Value + 1 UpdateForwardPointer(i) '''if''' rootCount[i].Value == 3: FixRootCount(i)</code> ===удаление Удаление дерева из кучи===

<code> Delete '''void''' delete('''int''' i, '''Node''' p): DeleteTree deleteTree(i, p) RootCount rootCount[i].Value = RootCountrootCount[i].Value - 1</code>

===Нахождение дерева с минимальным ключом в корне (<tex>MinKey\mathrm{minKey()}</tex>)=== <code> MinKey '''Node''' minKey() MinP minP = NULL '''for''' i = 0 to MaxRankmaxRank: p1 = MinKeyNodeRootminKeyNodeRoot(RootCountrootCount[i].ListPointerlistPointer) '''if''' GetKeygetKey(p1) < GetKeygetKey(MinPminP): MinP minP = p1 '''return''' MinP</code>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)===

===delete===Выполняем <codetex>\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> , преобразуем это DeleteViolation<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:maxRank '''if''' CountViolationcountViolation[i].Value == 2: FixCountViolation fixCountViolation(i) '''for''' i = 0 to h2.MaxRank:maxRank '''if''' CountViolationcountViolation[i].Value == 1: IncCountViolation incCountViolation(i, SearchBrothersearchBrother(CountViolationcountViolation[i].rmFirstviolation)) FixCountViolation fixCountViolation(i)</code>==См. также==* [[Тонкая куча]]

==Источникиинформации==* [http://www.intuit.ru/studies/courses/100/100/lecture/15432935?page=1 Толстые кучи — INTUIT.ru{{---}} Толстые кучи]* [httphttps://compscicenterwww.lektorium.ru/programtv/lecture/6829 приоритетные очереди - 14234 CS center{{---}} Приоритетные очереди]* [http://citeseerxwww.istcs.psutau.eduac.il/~haimk/viewdocpapers/summary?doi=10newthin1.1.1.145pdf H.8002 Haim Kaplan , Robert ER. Tarjan - . "Thin Heaps, Thick Heaps (". 2006)]