Изменения

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

Определяем '''толстое дерево''' (англ. ''Thick tree'') <tex>F_k</tex> ранга <tex>k</tex> <tex>~(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>, связанных тактаких, что корни двух из них являются самыми левыми потомками корня третьего.Ранг узла <tex>x</tex> в толстом дереве определяется как ранг толстого поддерева с корнем в узле <tex>x</tex>.

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

{{Утверждение|id=proposal1. |author= Свойства Толстых деревьев |about=|statement=В толстом дереве ранга <tex>k</tex> ровно <tex>3^k</tex> узлов.|proof=}}{{Определение|id=thin_forest_def|definition='''Толстый лес''' (англ. ''Thick forest'') {{---}} это набор толстых деревьев, ранги которых не обязательно попарно различны.}}

'''Свойства толстых деревьев:''' <br>*В толстом дереве ранга <tex>k</tex> ровно <tex>3^k</tex> узлов. <br>*Для любого натурального числа <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> деревьев.

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

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

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

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

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

* '''struct''' Node '''int''' key <texspan style="color:#008000">Key< //tex> {{---}} ключ элемента, приписанного узлу дерева</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>Parentleft</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>Lestx</tex> будем называть последовательность <tex>d = d_n, d_{{--n-1}} указатель на ближайшего левого брата*, \ldots, d_0</tex>Right, такую что</texdpi = "120"> x = {\sum\limits^{---n}_{i = 0} {d_i}}{b^i} указатель на ближайшего правого брата</tex> *где <tex>LChildd_i \in \{0, 1, \ldots, b\} </tex> , <tex> i \in \{{---0, 1, \ldots, n\} </tex>}} указатель на самого левого сына*{{Определение|id=|neat = |definition=Назовем <tex>Rankb</tex> {{--арное избыточное представление числа '''регулярным''', если в нем между любыми двумя цифрами, равными <tex>b</tex> , найдется цифра, отличная от <tex>b-1</tex>.}} ранг узла.

"Братья" связаны {{Определение|id=|neat = |definition=Пусть <tex>L(i)</tex> — номер разряда, отличного от <tex>b-1</tex> и ближайшего слева от <tex>i</tex>-го разряда в двусвязный список при помощи указателей регулярном <tex>Leftb</tex> и -арном избыточном представлении <tex>Rightd = 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>Leftd(L(i))=b</tex> ;*<tex>L'(i)</tex> — произвольное число <tex>>i</tex>, если <tex>d_i \in \{b-1, b-2\}</tex> и <tex>Rightd(L(i))<b-1</tex>; *<tex>L'(i) равен </tex> — не определено, если <tex>NULLd \notin \{b-1, b-2 \}</tex>.}}

===Фиксация цифры===Фиксацией цифры <tex>b</tex>, стоящей в <tex>i</[[Файл:ThickTreeExample.gif Пример толстых деревьев tex>-м разряде представления <tex>d</tex>F_0, F_1назовем операцию <tex>\mathrm{fix(i)}</tex>, F_2заключающуюся в обнулении цифры <tex>d_i</tex> и инкрементировании цифры <tex> d_{i+1} </tex>, F_3при этом если <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>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>MakeHeap\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>FindMin\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>Inserti</tex>-го разряда осуществляются за время <tex>O(key1)</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)===

* ===delete===Выполняем <tex>Delete</tex> {\mathrm{---decreaseKey}} <tex>O(\log(n))</tex>выполняем <tex>DecreaseKey</tex> а затем <tex>DeleteMin\mathrm{deleteMin}</tex>.* <tex>Meld===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> , если эта цифра имеет значение <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>Meld\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) ==См. также==* [[Тонкая куча]] ==Источники информации==* <tex>DeleteViolation<[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/tex>newthin1.pdf H.Kaplan, R.Tarjan. "Thin Heaps, Thick Heaps". 2006] [[Категория: Дискретная математика и алгоритмы]][[Категория: Приоритетные очереди]][[Категория: Структуры данных]]