Толстая куча на избыточном счётчике — различия между версиями
Slavian (обсуждение | вклад) (→Избыточное представление чисел) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 182 промежуточные версии 7 участников) | |||
Строка 1: | Строка 1: | ||
− | =Толстое дерево | + | ==Толстое дерево== |
+ | |||
{{Определение | {{Определение | ||
|id=def1. | |id=def1. | ||
|neat = 1 | |neat = 1 | ||
|definition= | |definition= | ||
− | Определяем '''толстое дерево''' <tex>F_k</tex> ранга <tex>k | + | Определяем '''толстое дерево''' (англ. ''Thick tree'') <tex>F_k</tex> ранга <tex>k ~(k = 0, 1, 2 ,\ldots )</tex> следующим образом: |
*Толстое дерево <tex>F_0</tex> ранга ноль состоит из единственного узла. <br> | *Толстое дерево <tex>F_0</tex> ранга ноль состоит из единственного узла. <br> | ||
− | *Толстое дерево <tex>F_k</tex> ранга <tex>k</tex>, для <tex>k = 1, 2, 3,\ | + | *Толстое дерево <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> в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления. | ||
+ | }} | ||
{{Утверждение | {{Утверждение | ||
Строка 20: | Строка 47: | ||
|about= | |about= | ||
|statement= | |statement= | ||
− | + | Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log{n})</tex> деревьев. | |
− | |||
− | |||
− | |||
|proof= | |proof= | ||
}} | }} | ||
+ | ==Толстые кучи== | ||
{{Определение | {{Определение | ||
|id=def2 | |id=def2 | ||
|neat = | |neat = | ||
|definition= | |definition= | ||
− | ''' | + | '''Лес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества. |
}} | }} | ||
{{Определение | {{Определение | ||
Строка 37: | Строка 62: | ||
|neat = | |neat = | ||
|definition= | |definition= | ||
− | '''Узел''' в | + | '''Узел''' (англ. ''Node'') в ''нагруженном лесе'' назовем '''неправильным''', если его ключ меньше ключа его родителя. |
}} | }} | ||
{{Определение | {{Определение | ||
Строка 45: | Строка 70: | ||
'''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</tex>. | '''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</tex>. | ||
}} | }} | ||
− | + | Здесь и далее ''Толстая куча на избыточном счетчике'' будет заменено на более лаконичное ''Толстая куча''. | |
− | |||
{{Определение | {{Определение | ||
|id=def5 | |id=def5 | ||
|neat = | |neat = | ||
|definition= | |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|Представление леса списком]] | ||
− | + | ==Избыточное представление чисел== | |
− | <tex> | + | {{Определение |
+ | |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> | + | где <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>. | ||
+ | }} | ||
{{Определение | {{Определение | ||
Строка 87: | Строка 123: | ||
|neat = | |neat = | ||
|definition= | |definition= | ||
− | + | Пусть <tex>L(i)</tex> — номер разряда, отличного от <tex>b-1</tex> и ближайшего слева от <tex>i</tex>-го разряда в регулярном <tex>b</tex>-арном избыточном представлении <tex>d = d_n, \ldots, d_0</tex>. | |
− | <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-арный''' счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной. | ||
==Корневой счетчик== | ==Корневой счетчик== | ||
Строка 98: | Строка 162: | ||
Значение его <tex>i</tex>-го разряда равно количеству деревьев ранга <tex>i</tex>, присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга <tex>i</tex> содержит ровно <tex>3^i</tex> узлов. | Значение его <tex>i</tex>-го разряда равно количеству деревьев ранга <tex>i</tex>, присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга <tex>i</tex> содержит ровно <tex>3^i</tex> узлов. | ||
Заметим, что состояние избыточного корневого представления определяется неоднозначно. Очевидно, что для любой толстой кучи, состоящей из <tex>n</tex> элементов, существует регулярное избыточное представление корневого счетчика. | Заметим, что состояние избыточного корневого представления определяется неоднозначно. Очевидно, что для любой толстой кучи, состоящей из <tex>n</tex> элементов, существует регулярное избыточное представление корневого счетчика. | ||
− | Списочный элемент, приписанный <tex>i</tex>-му разряду избыточного корневого представления, — это указатель на список деревьев ранга <tex>i</tex>, присутствующих в куче, образованный посредством указателей <tex> | + | Списочный элемент, приписанный <tex>i</tex>-му разряду избыточного корневого представления, — это указатель на список деревьев ранга <tex>i</tex>, присутствующих в куче, образованный посредством указателей <tex>right</tex> корневых узлов связываемых деревьев. |
{{Утверждение | {{Утверждение | ||
Строка 113: | Строка 177: | ||
}} | }} | ||
− | ''' | + | '''Корневой счетчик''' представляем расширяющимся массивом <tex>\mathtt{rootCount}</tex> , каждый элемент которого — запись с тремя полями: |
− | *<tex> | + | *<tex>\mathtt{rootCount[i].Value}</tex> {{---}} <tex>i</tex>-й разряд равный количеству деревьев ранга <tex>i</tex>. |
− | *<tex> | + | *<tex>\mathtt{rootCount[i].forwardPointer}</tex> {{---}} прямой указатель <tex>i</tex>-го разряда. |
− | *<tex> | + | *<tex>\mathtt{rootCount[i].listPointer}</tex> {{---}} указатель на список деревьев ранга <tex>i</tex>, присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя <tex>Right</tex> корневых узлов связываемых деревьев. Если в куче нет деревьев ранга <tex>i</tex> , то указатель <tex>\mathtt{listPointer}</tex> равен <tex>NULL</tex>. |
− | ''Заметим, что если значение равно нулю, то нам неважно значение указателя'' <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> | + | |
− | + | '''Счетчик нарушений''' состоит из расширенного избыточного двоичного представления и набора списочных элементов. | |
− | * <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> в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент. | Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга <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> счетчика нарушений. | Чтобы выполнить эту операцию, поступим следующим образом. Пусть <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/ | + | * [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] | ||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Приоритетные очереди]] | [[Категория: Приоритетные очереди]] | ||
+ | [[Категория: Структуры данных]] |
Текущая версия на 19:19, 4 сентября 2022
Содержание
- 1 Толстое дерево
- 2 Толстые кучи
- 3 Избыточное представление чисел
- 4 Корневой счетчик
- 4.1 Инициализация
- 4.2 Обновление прямого указателя
- 4.3 Корректировка при вставке
- 4.4 Корректировка при удалении
- 4.5 Связывание трех деревьев в одно
- 4.6 Значение ключа элемента по указателю
- 4.7 Узел с минимальным ключом
- 4.8 Операция фиксации
- 4.9 Инкрементирование i-го разряда корневого счетчика
- 4.10 Удаление дерева из кучи
- 4.11 Нахождение дерева с минимальным ключом в корне [math]\mathrm{minKey()}[/math]
- 5 Счетчик нарушений
- 6 Основные операции
- 7 См. также
- 8 Источники информации
Толстое дерево
- Толстое дерево
- Толстое дерево ранга , для , состоит из трех деревьев ранга ,таких, что корни двух из них являются самыми левыми потомками корня третьего.
Определение: |
Ранг узла | в толстом дереве определяется как ранг толстого поддерева с корнем в узле .
Свойства толстых деревьев
Утверждение: |
В толстом дереве ранга ровно узлов. |
Определение: |
Толстый лес (англ. Thick forest) — это набор толстых деревьев, ранги которых не обязательно попарно различны. |
Утверждение: |
Для любого натурального числа существует лес из толстых деревьев, в котором ровно узлов. |
Действительно, такой лес можно построить, включив в него столько деревьев ранга | , каково значение -го разряда представления числа в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
Утверждение: |
Толстый лес из узлов содержит деревьев. |
Толстые кучи
Определение: |
Лес будем называть нагруженным, если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества. |
Определение: |
Узел (англ. Node) в нагруженном лесе назовем неправильным, если его ключ меньше ключа его родителя. |
Определение: |
Нагруженный лес назовем почти кучеобразным, если для каждого значения | в нем имеется не более двух неправильных узлов ранга .
Здесь и далее Толстая куча на избыточном счетчике будет заменено на более лаконичное Толстая куча.
Определение: |
Толстая куча (англ. Thick heap, Fat heap) — это почти кучеобразный нагруженный лес. |
Структура узла
Каждый узел толстой кучи будем представлять записью со следующими полями:
struct Node int key // ключ элемента, приписанного узлу дерева Node parent // указатель на родителя узла Node left // указатель на ближайшего левого брата узла Node right // указатель на ближайшего правого брата узла Node lChild // указатель на самого левого сына int rank // ранг узла
"Братья" (узлы корневых деревьев, а также сыновья каждого узла) объединены в двусвязный список при помощи указателей
и . У самого левого (правого) "брата" в этом списке указатель ( ) равен .Структура кучи
Толстую кучу будем представлять записью следующего вида:
struct FatHeap int[] rootCount // массив, соответствующий корневому счетчику int[] countViolation // массив, соответствующий счетчику нарушений Node minPointer // указатель на элемент кучи с минимальным ключом int maxRank // наибольший ранг среди рангов деревьев, присутствующих в куче
Избыточное представление чисел
Определение: |
Избыточным где , | -арным представлением числа будем называть последовательность , такую что
Определение: |
Назовем | -арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами, равными , найдется цифра, отличная от .
Определение: |
Пусть
| — номер разряда, отличного от и ближайшего слева от -го разряда в регулярном -арном избыточном представлении .
Фиксация цифры
Фиксацией цифры
, стоящей в -м разряде представления , назовем операцию , заключающуюся в обнулении цифры и инкрементировании цифры , при этом если , то полагаем . При каждом выполнении операции фиксации будем обновлять значение . Очевидно, при операцию можно выполнить следующим образом: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
Инкремент
Операцию
инкрементирования -й цифры избыточного представления можно выполнить так:void inc(int i): fix(i) if (d[i] == b - 1) or (d[i] == b - 2) fix(L'[i]) d[i]++ fix(i)
Декремент
Эта схема может быть расширена для выполнения за константное время декрементирования произвольной цифры добавлением дополнительного цифрового значения
.Представление приоритетной очереди основано на использовании так называемых избыточных счетчиков, позволяющих за время
инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь один из способов реализации толстых куч. На самом деле, для их реализации подойдет произвольный d-арный счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.Корневой счетчик
Корневой счетчик состоит из избыточного троичного представления числа элементов в куче и набора списочных элементов.
Значение его
-го разряда равно количеству деревьев ранга , присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга содержит ровно узлов. Заметим, что состояние избыточного корневого представления определяется неоднозначно. Очевидно, что для любой толстой кучи, состоящей из элементов, существует регулярное избыточное представление корневого счетчика. Списочный элемент, приписанный -му разряду избыточного корневого представления, — это указатель на список деревьев ранга , присутствующих в куче, образованный посредством указателей корневых узлов связываемых деревьев.Утверждение (о корневом счетчике): |
Из определения корневого счетчика следует:
|
Корневой счетчик представляем расширяющимся массивом
, каждый элемент которого — запись с тремя полями:- — -й разряд равный количеству деревьев ранга .
- — прямой указатель -го разряда.
- — указатель на список деревьев ранга , присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя корневых узлов связываемых деревьев. Если в куче нет деревьев ранга , то указатель равен .
Заметим, что если значение равно нулю, то нам неважно значение указателя
.Инициализация
Чтобы время инициализации счетчиков было
, используем поразрядную их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную , которая показывает нам, какая часть массивов счетчиков используется в данный момент.При начальной инициализации необходимо установить счетчики в состояние, которое отвечает пустой куче. Очевидно, что в пустой куче не может быть никаких нарушений.
Обновление прямого указателя
Обновление прямого указателя
-го разряда корневого счетчика заключается в выполнении следующего псевдокода:void updateForwardPionter(int i): if rootCount[i + 1].Value == 3 - 1 rootCount[i].forwardPointer = rootCount[i + 1].forwardPointer else rootCount[i].forwardPointer = i + 1
Корректировка при вставке
Корректировка списочной части
-го разряда корневого счетчика при вставке в кучу нового дерева ранга . Эта процедура вставляет новое дерево ранга (на него указывает указатель ) в списочную часть -го разряда корневого счетчика выглядит так:void insertTree(int i, Node p):
p1 = rootCount[i].listPointer
if rootCount[i].Value
0
p.right = p1
else
p.right = NULL
p.left = NULL
rootCount[i].listPointer = p
Корректировка при удалении
Корректировка списочной части
-го разряда корневого счетчика при удалении из кучи дерева ранга . Эта процедура удаляет дерево ранга (на него указывает указатель ) из списочной части -го разряда корневого счетчика . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:void deleteTree(int i, Node p): p1 = rootCount[i].listPointer if p1 == p rootCount[i].listPointer = p.right j = 1 while (jrootCount[i].Value) and (p1.right p): j++ p1 = p1.right p1.right = p.right
Связывание трех деревьев в одно
Связывание
трех толстых деревьев ранга в одно толстое дерево ранга . Эта функция принимает три указателя на три разных толстых дерева одного и того же ранга и возвращает указатель на вновь сформированное дерево ранга . Процедура заключается в выполнении следующего псевдокода:Node fastening(Node p1, Node p2, Node p3): if (p1.keyp2.key) and (p1.Key p3.key) minP = p1 p1 = p2 p2 = p3 if (p2.key p1.key) and (p2.key p3.key) minP = p2 p1 = p1 p2 = p3 if (p3.key p1.key) and (p3.key 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 NULL minP.lChild.left = p2 minP.lChild = p1 minP.rank = minP.rank + 1 minP.right = NULL minP.left = NULL return minP
Значение ключа элемента по указателю
Функция
по указателю p на элемент определяет значение его ключа://поднужно понимать нейтральный относительно минимума элемент. int getKey(Node p): if p == NULL min = else min = p.key return min
Узел с минимальным ключом
Функция
, которая по указателю на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:Node minKeyNodeRoot(Node p):
p1 = p
minP = p1
while p1
NULL
if p1.key < minP.key
minP = p1
p1 = p1.right
return minP
Операция фиксации
Операция фиксации
для -го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга , состоящий ровно из трех деревьев. При выполнении этой операции значение в -м разряде — должно стать равным нулю, а значение в -м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга , а количество деревьев ранга должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга , связать их в дерево ранга и вставить вновь полученное дерево в кучу. Следует учесть, что ранг нового дерева может стать больше, чем , что потребует инициализации нового разряда. Для этого необходимо увеличить значение на единицу и заполнить новое поле, а также провести инициализацию нового разряда.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-го разряда корневого счетчика
По сравнению с описанным алгоритмом инкрементирования
-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.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)
Удаление дерева из кучи
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг
. Тогда значение -го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.void delete(int i, Node p): deleteTree(i, p) rootCount[i].Value = rootCount[i].Value - 1
Нахождение дерева с минимальным ключом в корне
Node minKey() minP = NULL for i = 0 to maxRank: p1 = minKeyNodeRoot(rootCount[i].listPointer) if getKey(p1) < getKey(minP): minP = p1 return minP
Счетчик нарушений
Заметим, что счетчик нарушений очень похож на корневой счетчик выше, но в отличие от второго:
- Нас теперь интересует не само число, а только значения разрядов.
- Операция фиксации тесно связана с толстой кучей.
Значение
-го разряда для счетчика нарушений интерпретируется как количество неправильных узлов ранга , а его списочная часть — это указатели на неправильные узлы ранга .Счетчик нарушений состоит из расширенного избыточного двоичного представления и набора списочных элементов.
Счетчик нарушений представлен саморасширяющимся массивом, элементы которого состоят из четырех полей:
- — количество неправильных узлов ранга в куче.
- — прямой указатель -го разряда
- — указатель на неправильный узел ранга
- — указатель на неправильный узел ранга
Утверждение (о счетчике нарушений): |
из определения счетчика нарушений следует:
|
Для инициализации нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга
. Это первый момент появления в куче узла ранга . Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного , соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.Основные операции
Рассмотрим операции, которые можно производить с толстой кучей. Время работы основных операций указано в таблице:
Операция | Время работы |
---|---|
makeHeap
Заключается в инициализации счетчиков.
findMin
Возвращает указатель на минимальный элемент.
insert(key)
Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга
в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.decreaseKey
Чтобы выполнить эту операцию, поступим следующим образом. Пусть
— узел, на который указывает указатель . Вычитаем из ключа узла . Если новый ключ меньше минимального ключа кучи , обмениваем ключ элемента с ключом минимального элемента. Новых нарушений операция не создаст. Пусть — ранг . Если — нарушаемый узел, добавляем как новое -ранговое нарушение инкрементированием -й цифры счетчика нарушений.deleteMin
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов. Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
delete
Выполняем
а затем .meld(h1, h2)
Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча —
. Пройти по счетчику нарушений от младшей цифры к старшей, пропуская цифры со значением . Для -й цифры делаем операцию фиксирования на каждой цифре, показываемой прямым указателем , если эта цифра имеет значение . Затем, если , фиксируем . Если , преобразуем это -ранговое нарушение в -ранговое нарушение, как при фиксировании, используя -рангового брата нарушенного узла вместо (несуществующего) другого -рангового нарушения. Как только не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика в корневой счетчик инкрементированием соответствующих цифр. Если минимальный узел содержит меньший ключ, чем минимальный узел , следует установить новым минимальным узлом минимальный узел . Затем нужно вернуть модифицированную кучу в качестве результата .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)