Просмотр исходного текста страницы Толстая куча на избыточном счётчике

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

{{Определение
|id=def1. 
|neat = 1
|definition=
Определяем '''толстое дерево''' (англ. ''Thick tree'') <tex>F_k</tex> ранга <tex>k ~(k = 0, 1, 2 ,\ldots )</tex> следующим образом:
*Толстое дерево <tex>F_0</tex> ранга ноль состоит из единственного узла. <br>
*Толстое дерево <tex>F_k</tex>  ранга <tex>k</tex>, для <tex>k = 1, 2, 3,\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</tex> ровно <tex>3^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> в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
}}

{{Утверждение
|id=proposal1. 
|author=
|about=
|statement=
Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log{n})</tex> деревьев.
|proof=
}}

==Толстые кучи==
{{Определение
|id=def2 
|neat =
|definition=
'''Лес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.
}}
{{Определение
|id=def3 
|neat =
|definition=
'''Узел''' (англ. ''Node'') в ''нагруженном лесе'' назовем '''неправильным''', если его ключ меньше ключа его родителя.
}}
{{Определение
|id=def4 
|neat =
|definition=
'''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</tex>.
}}
Здесь и далее ''Толстая куча на избыточном счетчике'' будет заменено на более лаконичное ''Толстая куча''.
{{Определение
|id=def5 
|neat =
|definition=
'''Толстая куча''' (англ. ''Thick heap, Fat heap'') — это '''почти кучеобразный''' '''нагруженный лес'''.
}}

=== Структура узла ===
Каждый узел толстой кучи будем представлять записью со следующими полями:
 '''struct''' Node
   '''int''' key <span style="color:#008000">      // ключ элемента, приписанного узлу дерева</span>
   '''Node''' parent <span style="color:#008000">  // указатель на родителя узла</span>
   '''Node''' left <span style="color:#008000">    // указатель на ближайшего левого брата узла</span>
   '''Node''' right <span style="color:#008000">   // указатель на ближайшего правого брата узла</span>
   '''Node''' lChild <span style="color:#008000">  // указатель на самого левого сына</span>
   '''int''' rank <span style="color:#008000">     // ранг узла</span>

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

===Структура кучи===
Толстую кучу будем представлять записью следующего вида:

 '''struct''' FatHeap
   '''int[]''' rootCount <span style="color:#008000">       // массив, соответствующий корневому счетчику</span>
   '''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>d = d_n, d_{n-1}, \ldots, d_0</tex>, такую что
<tex dpi = "120">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>
}}

{{Определение
|id=
|neat = 
|definition=
Назовем   <tex>b</tex>-арное избыточное представление числа '''регулярным''', если в нем между любыми двумя цифрами, равными <tex>b</tex> , найдется цифра, отличная от <tex>b-1</tex>.
}}

{{Определение
|id=
|neat = 
|definition=
Пусть  <tex>L(i)</tex> — номер разряда, отличного от  <tex>b-1</tex> и ближайшего слева от   <tex>i</tex>-го разряда в регулярном   <tex>b</tex>-арном избыточном представлении <tex>d = d_n, \ldots, d_0</tex>.
<br>
'''Прямой указатель''' <tex>L'(i)</tex> определим  следующим образом: 
*<tex>L'(i) = L(i)</tex> , если <tex>d_i \in \{b-1, b-2\}</tex> и <tex>d(L(i))=b</tex>;
*<tex>L'(i)</tex> — произвольное число <tex>>i</tex>, если <tex>d_i \in \{b-1, b-2\}</tex> и <tex>d(L(i))<b-1</tex>; 
*<tex>L'(i)</tex>  — не определено, если <tex>d \notin \{b-1, b-2 \}</tex> .
}}

===Фиксация цифры===
Фиксацией цифры <tex>b</tex>, стоящей в <tex>i</tex>-м разряде представления <tex>d</tex>, назовем операцию <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>\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{inc(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>O(1)</tex> инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь '''один из способов реализации''' толстых куч. На самом деле, для их реализации подойдет '''произвольный d-арный''' счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.

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

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

{{Утверждение
|id=proposal2. 
|author=
|about=о корневом счетчике
|statement=
Из определения корневого счетчика следует:
*Корневой счетчик позволяет иметь доступ к корню любого дерева ранга <tex>i</tex>  за время <tex>O(1)</tex>.
*Вставка толстого дерева ранга <tex>i</tex>  соответствует операции инкрементирования  <tex>i</tex>-го разряда корневого счетчика.
*Удаление толстого поддерева ранга  <tex>i</tex> соответствует операции декрементирования <tex>i</tex>-го разряда корневого счетчика.
*Операции инкрементирования и декрементирования <tex>i</tex>-го разряда корневого счетчика осуществляются за время <tex>O(1)</tex>.
|proof=
}}

'''Корневой счетчик''' представляем расширяющимся массивом <tex>\mathtt{rootCount}</tex> , каждый элемент которого — запись с тремя полями:
*<tex>\mathtt{rootCount[i].Value}</tex> {{---}} <tex>i</tex>-й разряд равный количеству деревьев ранга <tex>i</tex>.
*<tex>\mathtt{rootCount[i].forwardPointer}</tex> {{---}} прямой указатель <tex>i</tex>-го разряда.
*<tex>\mathtt{rootCount[i].listPointer}</tex> {{---}} указатель на список деревьев ранга <tex>i</tex>, присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя <tex>Right</tex>  корневых узлов связываемых деревьев. Если в куче нет деревьев ранга <tex>i</tex> , то указатель <tex>\mathtt{listPointer}</tex> равен <tex>NULL</tex>. 
''Заметим, что если значение   равно нулю, то нам неважно значение указателя'' <tex>\mathtt{rootCount[i].listPointer}</tex>.

===Инициализация===
Чтобы время инициализации счетчиков было <tex>O(1)</tex>, используем '''поразрядную''' их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную <tex>\mathtt{maxRank}</tex>, которая показывает нам, какая часть массивов счетчиков используется в данный момент.

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

===Обновление прямого указателя===
Обновление прямого указателя <tex>i</tex>-го разряда корневого счетчика заключается в выполнении следующего псевдокода:
 '''void''' updateForwardPionter('''int''' i):
   '''if''' rootCount[i + 1].Value == 3 - 1
     rootCount[i].forwardPointer = rootCount[i + 1].forwardPointer
   '''else'''
     rootCount[i].forwardPointer = i + 1

===Корректировка при вставке ===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при вставке в кучу нового дерева ранга <tex>i~(\mathrm{insertTree(i,p)})</tex>. Эта процедура вставляет новое дерево ранга  <tex>i</tex> (на него указывает указатель <tex>p</tex>) в списочную часть  <tex>i</tex>-го разряда корневого счетчика <tex>\mathtt{rootCount}</tex> выглядит так:
 '''void''' insertTree('''int''' i, '''Node''' p):
   p1 = rootCount[i].listPointer
   '''if''' rootCount[i].Value <tex> \ne </tex> 0
     p.right = p1
   '''else'''
     p.right = NULL
   p.left = NULL
   rootCount[i].listPointer = p

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

===Связывание трех деревьев в одно===
'''Связывание''' <tex>\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):
   '''if''' (p1.key <tex> \leqslant </tex> p2.key) '''and''' (p1.Key <tex> \leqslant </tex> p3.key)
     minP = p1
     p1 = p2
     p2 = p3
   '''if''' (p2.key <tex> \leqslant </tex> p1.key) '''and''' (p2.key <tex> \leqslant </tex> p3.key)
     minP = p2
     p1 = p1
     p2 = p3
   '''if''' (p3.key <tex> \leqslant </tex> p1.key) '''and''' (p3.key <tex> \leqslant </tex> p2.key)
     minP = p3
     p1 = p1
     p2 = p2
   p1.right = p2
   p1.left = NULL
   p1.parent = minP
   p2.right = minP.lChild
   p2.left = p1
   p2.parent = minP
   '''if''' minP.lChild <tex> \ne </tex> NULL
     minP.lChild.left = p2
   minP.lChild = p1
   minP.rank = minP.rank + 1
   minP.right = NULL
   minP.left = NULL
   '''return''' minP

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

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

Функция <tex>\mathrm{minKeyNodeRoot(p)}</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:
 '''Node''' minKeyNodeRoot('''Node''' p):
   p1 = p
   minP = p1
   '''while''' p1 <tex> \ne </tex> NULL
     '''if''' p1.key < minP.key
       minP = p1
       p1 = p1.right
   '''return''' 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}</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
 '''void''' rmFixRootCount('''int''' i)
   '''if''' maxRank == i
     maxRank = i + 1
     rootCount[i + 1].Value = 0
     countViolation[i + 1].Value = 0
   '''else'''
     updateForwardPointer(i + 1)
   rootCount[i].Value = 0
   p1 = rootCount[i].listPointer
   p2 = p1.right
   p3 = p2.right
   p = fastening(p1, p2, p3)
   rootCount[i].listPointer = NULL
   insertTree(i + 1, p)
   rootCount[i + 1].Value = rootCount[i + 1].Value + 1

===Инкрементирование 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);
   '''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)

===Удаление дерева из кучи===
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>i</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
 '''void''' delete('''int''' i, '''Node''' p):
   deleteTree(i, p)
   rootCount[i].Value = rootCount[i].Value - 1

===Нахождение дерева с минимальным ключом в корне <tex>\mathrm{minKey()}</tex>===
 '''Node''' minKey()
   minP = NULL
   '''for''' i = 0 to maxRank:
     p1 = minKeyNodeRoot(rootCount[i].listPointer)
     '''if''' getKey(p1) < getKey(minP):
       minP = p1
   '''return''' minP

==Счетчик нарушений==
Заметим, что '''счетчик нарушений''' очень похож на '''корневой счетчик''' выше, но в отличие от второго:
*Нас теперь интересует не само число, а только значения разрядов.
*Операция фиксации тесно связана с толстой кучей.

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

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

'''Счетчик нарушений''' представлен [[Саморасширяющийся массив|саморасширяющимся массивом]], элементы которого состоят из четырех полей:
*<tex>\mathtt{countViolation[i].Value}</tex> {{---}} количество неправильных узлов ранга <tex>i</tex> в куче.
*<tex>\mathtt{countViolation[i].forvardPointer}</tex> {{---}} прямой указатель <tex>i</tex>-го разряда
*<tex>\mathtt{countViolation[i].firstViolation}</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>
*<tex>\mathtt{countViolation[i].secondViolation}</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>

{{Утверждение
|id=
|author=
|about= о счетчике нарушений
|statement=
из определения '''счетчика нарушений''' следует:
*Наличие счетчика нарушений позволяет иметь доступ к любому неправильному узлу ранга  <tex>i</tex> за время <tex>O(1)</tex> .
*Уменьшение ключа у элемента ранга  <tex>i</tex> соответствует операции инкрементирования  <tex>i</tex>-го разряда счетчика нарушений ''(естественно, лишь в случае, когда новое значение ключа у изменяемого узла становится меньше значения ключа его родителя)''.
*Операции инкрементирования и декрементирования   <tex>i</tex>-го разряда осуществляются за время  <tex>O(1)</tex>.
|proof=
}}

Для '''инициализации''' нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга <tex>\mathtt{maxRank + 1}</tex>. Это первый момент появления в куче узла ранга <tex>\mathtt{maxRank + 1}</tex>. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного <tex>\mathtt{maxRank + 1}</tex>, соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.

==Основные операции==
Рассмотрим операции, которые можно производить с толстой кучей. Время работы основных операций указано в таблице:
{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
! Операция || Время работы 
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm{makeHeap}</tex>||<tex>O(1)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm{findMin}</tex>||<tex>O(1)</tex>
|-align="center" bgcolor=#FFFFFF
||<tex>\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>\mathrm{deleteMin}</tex>||<tex>O(\log(n))</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(\log(n))</tex>
|}

===makeHeap===
Заключается в инициализации счетчиков.
 
===findMin===
Возвращает указатель на минимальный элемент.
 
===insert(key)===
Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга <tex>0</tex> в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.

===decreaseKey===
Чтобы выполнить эту операцию, поступим следующим образом. Пусть <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>  счетчика нарушений.

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

===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/2935?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".  2006]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]