Толстая куча на избыточном счётчике — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Инкрементирование i-го разряда корневого счетчика)
м (rollbackEdits.php mass rollback)
 
(не показано 107 промежуточных версий 5 участников)
Строка 1: Строка 1:
=Толстое дерево=
+
==Толстое дерево==
  
 
{{Определение
 
{{Определение
Строка 5: Строка 5:
 
|neat = 1
 
|neat = 1
 
|definition=
 
|definition=
Определяем '''толстое дерево''' (англ. ''Fat Heap'') <tex>F_k</tex> ранга <tex>k ~(k = 0, 1, 2 ~\dots )</tex> следующим образом:
+
Определяем '''толстое дерево''' (англ. ''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,\dots </tex>, состоит из трех деревьев  <tex>F_{k-1}</tex> ранга <tex>k</tex>,таких, что корни двух из них являются самыми левыми потомками корня третьего.
+
*Толстое дерево <tex>F_k</tex>  ранга <tex>k</tex>, для <tex>k = 1, 2, 3,\ldots </tex>, состоит из трех деревьев  <tex>F_{k-1}</tex> ранга <tex>k-1</tex>,таких, что корни двух из них являются самыми левыми потомками корня третьего.
Ранг узла <tex>x</tex> в толстом дереве определяется как ранг толстого поддерева с корнем в узле <tex>x</tex>.  
 
 
}}
 
}}
[[Файл:FatTreesExample.png |400px|thumb|left|Пример толстых деревьев <tex>F_0, F_1, F_2, F_3</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> в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
 +
}}
  
 
{{Утверждение
 
{{Утверждение
Строка 18: Строка 47:
 
|about=
 
|about=
 
|statement=
 
|statement=
'''Свойства толстых деревьев:''' <br>
+
Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log{n})</tex> деревьев.
*В толстом дереве ранга <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> деревьев.
 
 
|proof=
 
|proof=
 
}}
 
}}
  
 +
==Толстые кучи==
 
{{Определение
 
{{Определение
 
|id=def2  
 
|id=def2  
Строка 43: Строка 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'') — это '''почти кучеобразный''' '''нагруженный лес'''.
 
}}
 
}}
  
==Представление толстой кучи==
+
=== Структура узла ===
 
Каждый узел толстой кучи будем представлять записью со следующими полями:
 
Каждый узел толстой кучи будем представлять записью со следующими полями:
*<tex>Key</tex> {{---}} ключ элемента, приписанного узлу дерева
+
'''struct''' Node
*<tex>Parent</tex> {{---}} указатель на родителя
+
  '''int''' key <span style="color:#008000">     // ключ элемента, приписанного узлу дерева</span>
*<tex>Left</tex> {{---}} указатель на ближайшего левого брата
+
  '''Node''' parent <span style="color:#008000"> // указатель на родителя узла</span>
*<tex>Right</tex> {{---}} указатель на ближайшего правого брата
+
  '''Node''' left <span style="color:#008000">   // указатель на ближайшего левого брата узла</span>
*<tex>LChild</tex> {{---}} указатель на самого левого сына
+
  '''Node''' right <span style="color:#008000">   // указатель на ближайшего правого брата узла</span>
*<tex>Rank</tex> {{---}} ранг узла.
+
  '''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>.
 
 
 
[[Файл:FatHeapExample.png |400px|thumb|right|Представление леса списком]]
 
  
=Вспомогательные структуры=
+
"Братья" (узлы корневых деревьев, а также сыновья каждого узла) объединены в двусвязный список при помощи указателей <tex>left</tex> и <tex>right</tex>. У самого левого (правого) "брата" в этом списке указатель <tex>left</tex> (<tex>right</tex>) равен <tex>NULL</tex>.
Нам понадобятся понятия '''корневого счетчика''' и '''счетчика нарушений'''.
 
  
 +
===Структура кучи===
 
Толстую кучу будем представлять записью следующего вида:
 
Толстую кучу будем представлять записью следующего вида:
<tex>FatHeap = (RootCount, CountViolation, Minpointer, MaxRank)</tex>, где:
 
 
<tex>RootCount</tex> {{---}} массив, соответствующий '''корневому счетчику'''
 
 
<tex>CountViolation</tex> {{---}} массив, соответствующий '''счетчику нарушений'''
 
 
<tex>MinPointer</tex> {{---}} указатель на элемент кучи с '''минимальным ключом'''
 
  
<tex>MaxRank</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|Представление леса списком]]
  
 
==Избыточное представление чисел==
 
==Избыточное представление чисел==
Строка 88: Строка 106:
 
|neat =  
 
|neat =  
 
|definition=
 
|definition=
'''Избыточным''' <tex>b</tex>-арным представлением числа <tex>x</tex> будем называть последовательность <tex>d = d_n, d_{n-1}, ... d_0</tex>, такую что
+
'''Избыточным''' <tex>b</tex>-арным представлением числа <tex>x</tex> будем называть последовательность <tex>d = d_n, d_{n-1}, \ldots, d_0</tex>, такую что
<tex dpi = "150">x = {\sum\limits^{n}_{i = 0} {d_i}}{b^i}</tex>
+
<tex dpi = "120">x = {\sum\limits^{n}_{i = 0} {d_i}}{b^i}</tex>
  
где <tex> d_i \in \{0, 1, ..., b\} </tex>, <tex> i \in \{0, 1, ..., n\} </tex>
+
где <tex> d_i \in \{0, 1, \ldots, b\} </tex>, <tex> i \in \{0, 1, \ldots, n\} </tex>
 
}}
 
}}
  
Строка 105: Строка 123:
 
|neat =  
 
|neat =  
 
|definition=
 
|definition=
Пусть  <tex>L(i)</tex> — номер разряда, отличного от  <tex>b-1</tex> и ближайшего слева от  <tex>i</tex>-го разряда в регулярном  <tex>b</tex>-арном избыточном представлении <tex>d = d_n, ... d_0</tex>.
+
Пусть  <tex>L(i)</tex> — номер разряда, отличного от  <tex>b-1</tex> и ближайшего слева от  <tex>i</tex>-го разряда в регулярном  <tex>b</tex>-арном избыточном представлении <tex>d = d_n, \ldots, d_0</tex>.
 
<br>
 
<br>
Определим <tex>L'(i)</tex>  следующим образом:  
+
'''Прямой указатель''' <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) = 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>>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>L'(i)</tex>  — не определено, если <tex>d \notin \{b-1, b-2 \}</tex> .
<br>
 
Величину  <tex>L'(i)</tex> будем называть прямым указателем.
 
 
}}
 
}}
  
 
===Фиксация цифры===
 
===Фиксация цифры===
Фиксацией цифры <tex>b</tex>, стоящей в <tex>i</tex>-м разряде представления <tex>d</tex>, (Fix(i)) назовем операцию, заключающуюся в обнулении цифры <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(i)</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>  можно выполнить следующим образом:
<code>
+
'''void''' fix('''int''' i):
    fix('''int''' i):
+
  '''if''' d[i] == b
    '''if''' d[i] == b
+
    d[i] = 0
      d[i] = 0
+
    d[i + 1]++
      d[i + 1]++
+
  '''if''' d[i + 1] == b - 1:
    '''if''' d[i + 1] == b - 1:
+
    L'[i] = L'[i + 1]
      L'[i] = L'[i + 1]
+
  '''else'''
    '''else'''
+
    L'[i] = i + 1
      L'[i] = i + 1
 
</code>
 
  
 
===Инкремент===
 
===Инкремент===
Инкрементирование <tex>i</tex>-й цифры избыточного представления <tex>d</tex> <tex>Inc(i)</tex> можно выполнить так:
+
Операцию <tex>\mathrm{inc(i)}</tex> инкрементирования <tex>i</tex>-й цифры избыточного представления <tex>d</tex> можно выполнить так:
<code>
+
'''void''' inc('''int''' i):
  inc('''int''' i):
+
  fix(i)
    fix(i)
+
  '''if''' (d[i] == b - 1) '''or''' (d[i] == b - 2)
    '''if''' (d[i] == b - 1) '''or''' (d[i] == b - 2)
+
    fix(L'[i])
      fix(L'[i])
+
  d[i]++
    d[i]++
+
  fix(i)
    fix(i)
 
</code>
 
  
 
===Декремент===
 
===Декремент===
  
 
Эта схема может быть расширена для выполнения за константное время декрементирования произвольной цифры добавлением дополнительного цифрового значения <tex>b+1</tex>.
 
Эта схема может быть расширена для выполнения за константное время декрементирования произвольной цифры добавлением дополнительного цифрового значения <tex>b+1</tex>.
 
 
  
 
Представление приоритетной очереди основано на использовании так называемых '''избыточных счетчиков''', позволяющих за время <tex>O(1)</tex> инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь '''один из способов реализации''' толстых куч. На самом деле, для их реализации подойдет '''произвольный d-арный''' счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.
 
Представление приоритетной очереди основано на использовании так называемых '''избыточных счетчиков''', позволяющих за время <tex>O(1)</tex> инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь '''один из способов реализации''' толстых куч. На самом деле, для их реализации подойдет '''произвольный d-арный''' счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.
Строка 152: Строка 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>Right</tex> корневых узлов связываемых деревьев.
+
Списочный элемент, приписанный <tex>i</tex>-му разряду избыточного корневого представления, — это указатель на список деревьев ранга <tex>i</tex>, присутствующих в куче, образованный посредством указателей <tex>right</tex> корневых узлов связываемых деревьев.
  
 
{{Утверждение
 
{{Утверждение
Строка 167: Строка 177:
 
}}
 
}}
  
'''Корневой счетчик''' представляем расширяющимся массивом <tex>RootCount</tex> , каждый элемент которого — запись с тремя полями:
+
'''Корневой счетчик''' представляем расширяющимся массивом <tex>\mathtt{rootCount}</tex> , каждый элемент которого — запись с тремя полями:
*<tex>RootCount[i].Value</tex> {{---}} <tex>i</tex>-й разряд равный количеству деревьев ранга <tex>i</tex>.
+
*<tex>\mathtt{rootCount[i].Value}</tex> {{---}} <tex>i</tex>-й разряд равный количеству деревьев ранга <tex>i</tex>.
*<tex>RootCount[i].ForwardPointer</tex> {{---}} прямой указатель <tex>i</tex>-го разряда.
+
*<tex>\mathtt{rootCount[i].forwardPointer}</tex> {{---}} прямой указатель <tex>i</tex>-го разряда.
*<tex>RootCount[i].ListPointer</tex> {{---}} указатель на список деревьев ранга <tex>i</tex>, присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя <tex>Right</tex>  корневых узлов связываемых деревьев. Если в куче нет деревьев ранга <tex>i</tex> , то указатель <tex>ListPointer</tex> равен <tex>NULL</tex>.  
+
*<tex>\mathtt{rootCount[i].listPointer}</tex> {{---}} указатель на список деревьев ранга <tex>i</tex>, присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя <tex>Right</tex>  корневых узлов связываемых деревьев. Если в куче нет деревьев ранга <tex>i</tex> , то указатель <tex>\mathtt{listPointer}</tex> равен <tex>NULL</tex>.  
''Заметим, что если значение  равно нулю, то нам неважно значение указателя'' <tex>RootCount[i].ListPointer</tex>.
+
''Заметим, что если значение  равно нулю, то нам неважно значение указателя'' <tex>\mathtt{rootCount[i].listPointer}</tex>.
  
 
===Инициализация===
 
===Инициализация===
Чтобы время инициализации счетчиков было <tex>O(1)</tex>, используем '''поразрядную''' их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную <tex>MaxRank</tex>, которая показывает нам, какая часть массивов счетчиков используется в данный момент.
+
Чтобы время инициализации счетчиков было <tex>O(1)</tex>, используем '''поразрядную''' их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную <tex>\mathtt{maxRank}</tex>, которая показывает нам, какая часть массивов счетчиков используется в данный момент.
  
 
При начальной инициализации необходимо установить счетчики в состояние, которое отвечает '''пустой куче'''. Очевидно, что в пустой куче не может быть никаких нарушений.
 
При начальной инициализации необходимо установить счетчики в состояние, которое отвечает '''пустой куче'''. Очевидно, что в пустой куче не может быть никаких нарушений.
Строка 180: Строка 190:
 
===Обновление прямого указателя===
 
===Обновление прямого указателя===
 
Обновление прямого указателя <tex>i</tex>-го разряда корневого счетчика заключается в выполнении следующего псевдокода:
 
Обновление прямого указателя <tex>i</tex>-го разряда корневого счетчика заключается в выполнении следующего псевдокода:
<code>
+
'''void''' updateForwardPionter('''int''' i):
  updateForwardPionter('''int''' i):
+
  '''if''' rootCount[i + 1].Value == 3 - 1
    '''if''' rootCount[i + 1].Value == 3 - 1
+
    rootCount[i].forwardPointer = rootCount[i + 1].forwardPointer
      rootCount[i].forwardPointer = rootCount[i + 1].forwardPointer
+
  '''else'''
    '''else'''
+
    rootCount[i].forwardPointer = i + 1
      rootCount[i].forwardPointer = i + 1
 
</code>
 
  
 
===Корректировка при вставке ===
 
===Корректировка при вставке ===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при вставке в кучу нового дерева ранга <tex>i~(InsertTree(i,p))</tex>. Эта процедура вставляет новое дерево ранга  <tex>i</tex> (на него указывает указатель <tex>p</tex>) в списочную часть  <tex>i</tex>-го разряда корневого счетчика <tex>RootCount</tex> выглядит так:
+
Корректировка списочной части <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):
<code>
+
  p1 = rootCount[i].listPointer
  insertTree(i, p):
+
  '''if''' rootCount[i].Value <tex> \ne </tex> 0
    p1 = rootCount[i].listPointer
+
    p.right = p1
    '''if''' rootCount[i].Value <tex> \ne </tex> 0:
+
  '''else'''
      p.right = p1
+
    p.right = NULL
    '''else''':
+
  p.left = NULL
      p.right = NULL
+
  rootCount[i].listPointer = p
    p.left = NULL
 
    rootCount[i].listPointer = p
 
</code>
 
  
 
===Корректировка при удалении===
 
===Корректировка при удалении===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при удалении из кучи дерева ранга <tex>i~(DeleteTree(i,p))</tex>. Эта процедура удаляет дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) из списочной части  <tex>i</tex>-го разряда корневого счетчика <tex>RootCount</tex> . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:
+
Корректировка списочной части <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):
<code>
+
  p1 = rootCount[i].listPointer
  deleteTree(i, p):
+
  '''if''' p1 == p
    p1 = rootCount[i].listPointer
+
    rootCount[i].listPointer = p.right
    '''if''' p1 == p
+
  j = 1
      rootCount[i].listPointer = p.right
+
  '''while''' (j <tex> \leqslant </tex> rootCount[i].Value) '''and''' (p1.right <tex> \ne </tex> p):
    j = 1
+
    j++
    '''while''' (j <tex> \le </tex> rootCount[i].Value) '''and''' (p1.right <tex> \ne </tex> p):
+
    p1 = p1.right
      j++
+
  p1.right = p.right
      p1 = p1.right
 
    p1.right = p.right
 
</code>
 
  
 
===Связывание трех деревьев в одно===
 
===Связывание трех деревьев в одно===
'''Связывание''' <tex>(fastening (p1, p2, p3))</tex> трех толстых деревьев ранга <tex>i</tex> в одно толстое дерево ранга <tex>i+1</tex>. Эта функция принимает три указателя <tex>(p1, p2 ,p3)</tex>  на три разных толстых дерева одного и того же ранга <tex>i</tex>  и возвращает указатель на вновь сформированное дерево ранга <tex>i+1</tex> .
+
'''Связывание''' <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):
<code>
+
  '''if''' (p1.key <tex> \leqslant </tex> p2.key) '''and''' (p1.Key <tex> \leqslant </tex> p3.key)
  fastening (p1, p2, p3):
+
    minP = p1
    '''if''' (p1.key <tex> \le </tex> p2.key) '''and''' (p1.Key <tex> \le </tex> p3.key)
+
    p1 = p2
      minP = p1
+
    p2 = p3
      p1 = p2
+
  '''if''' (p2.key <tex> \leqslant </tex> p1.key) '''and''' (p2.key <tex> \leqslant </tex> p3.key)
      p2 = p3
+
    minP = p2
    '''if''' (p2.key <tex> \le </tex> p1.key) '''and''' (p2.key <tex> \le </tex> p3.key)
+
    p1 = p1
      minP = p2
+
    p2 = p3
      p1 = p1
+
  '''if''' (p3.key <tex> \leqslant </tex> p1.key) '''and''' (p3.key <tex> \leqslant </tex> p2.key)
      p2 = p3
+
    minP = p3
    '''if''' (p3.key <tex> \le </tex> p1.key) '''and''' (p3.key <tex> \le </tex> p2.key)
+
    p1 = p1
      minP = p3
+
    p2 = p2
      p1 = p1
+
  p1.right = p2
      p2 = p2
+
  p1.left = NULL
    p1.right = p2
+
  p1.parent = minP
    p1.left = NULL
+
  p2.right = minP.lChild
    p1.parent = minP
+
  p2.left = p1
    p2.right = minP.lChild
+
  p2.parent = minP
    p2.left = p1
+
  '''if''' minP.lChild <tex> \ne </tex> NULL
    p2.parent = minP
+
    minP.lChild.left = p2
    '''if''' minP.lChild <tex> \ne </tex> NULL
+
  minP.lChild = p1
      minP.lChild.left = p2
+
  minP.rank = minP.rank + 1
    minP.lChild = p1
+
  minP.right = NULL
    minP.rank = minP.rank + 1
+
  minP.left = NULL
    minP.right = NULL
+
  '''return''' minP
    minP.left = NULL
 
    '''return''' minP
 
</code>
 
  
 
===Значение ключа элемента по указателю===
 
===Значение ключа элемента по указателю===
Функция <tex>getKey(p)</tex> по указателю p на элемент определяет значение его ключа:
+
Функция <tex>\mathrm{getKey(p)}</tex> по указателю p на элемент определяет значение его ключа:
 
+
<font color=green>//под <tex>\infty</tex> нужно понимать нейтральный относительно минимума элемент.</font>
// ''под <tex>\infty</tex> нужно понимать нейтральный относительно минимума элемент.''
+
'''int''' getKey('''Node''' p):
 
+
  '''if''' p == NULL
<code>
+
    min = <tex>\infty</tex>
  getKey(p):
+
  '''else'''
    '''if''' p == NULL
+
    min = p.key
      min = <tex>\infty</tex>
+
  '''return''' min
    '''else'''
 
      min = p.key
 
    '''return''' min  
 
</code>
 
  
 
===Узел с минимальным ключом===
 
===Узел с минимальным ключом===
  
Функция <tex>minKeyNodeRoot(p)</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:
+
Функция <tex>\mathrm{minKeyNodeRoot(p)}</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:
<code>
+
'''Node''' minKeyNodeRoot('''Node''' p):
  minKeyNodeRoot(p):
+
  p1 = p
    p1 = p
+
  minP = p1
    minP = p1
+
  '''while''' p1 <tex> \ne </tex> NULL
    '''while''' p1 <tex> \ne </tex> NULL
+
    '''if''' p1.key < minP.key
      '''if''' p1.key < minP.key
+
      minP = p1
        minP = p1
+
      p1 = p1.right
        p1 = p1.right
+
  '''return''' minP
    '''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> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
 
  
<code>
+
===Операция фиксации ===
  rmFixRootCount(i)
+
Операция фиксации <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> и вставить вновь полученное дерево в кучу.
    '''if''' maxRank == i:
+
Следует учесть, что ранг нового дерева может стать больше, чем <tex>\mathtt{maxRank}</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>\mathtt{maxRank}</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
      maxRank = i + 1
+
'''void''' rmFixRootCount('''int''' i)
      rootCount[i + 1].Value = 0
+
  '''if''' maxRank == i
      countViolation[i + 1].Value = 0
+
    maxRank = i + 1
    '''else''':
+
    rootCount[i + 1].Value = 0
      updateForwardPointer(i + 1)
+
    countViolation[i + 1].Value = 0
    rootCount[i].Value = 0
+
  '''else'''
    p1 = rootCount[i].listPointer
+
    updateForwardPointer(i + 1)
    p2 = p1.right
+
  rootCount[i].Value = 0
    p3 = p2.right
+
  p1 = rootCount[i].listPointer
    p = fastening(p1, p2, p3)
+
  p2 = p1.right
    rootCount[i].listPointer = NULL
+
  p3 = p2.right
    insertTree(i + 1, p)
+
  p = fastening(p1, p2, p3)
    rootCount[i + 1].Value = rootCount[i + 1].Value + 1  
+
  rootCount[i].listPointer = NULL
</code>
+
  insertTree(i + 1, p)
 +
  rootCount[i + 1].Value = rootCount[i + 1].Value + 1
  
 
===Инкрементирование i-го разряда корневого счетчика===
 
===Инкрементирование i-го разряда корневого счетчика===
 
По сравнению с описанным алгоритмом инкрементирования <tex>i</tex>-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
 
По сравнению с описанным алгоритмом инкрементирования <tex>i</tex>-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
 
+
'''void''' rmIncRootCount('''int''' i, '''Node''' p)
<code>
+
  '''if''' (rootCount[i].Value == 1) '''or''' (rootCount[i].Value == 2)
  rmIncRootCount(i,p)
+
    '''if''' rootCount[rootCount[i].forwardPointer].Value == 3
    '''if''' (rootCount[i].Value == 1) '''or''' (rootCount[i].Value == 2)
+
      fixRootCount(rootCount[i].forwardPointer);
      '''if''' rootCount[rootCount[i].forwardPointer].Value == 3
+
  '''if''' rootCount[i].Value == 3
        fixRootCount(rootCount[i].forwardPointer);
+
    fixRootCount(i)
    '''if''' rootCount[i].Value == 3
+
  insertTree(i, p)
      fixRootCount(i)
+
  rootCount[i].Value = rootCount[i].Value + 1
    insertTree(i, p)
+
  updateForwardPointer(i)
    rootCount[i].Value = rootCount[i].Value + 1
+
  '''if''' rootCount[i].Value == 3
    updateForwardPointer(i)
+
    fixRootCount(i)
    '''if''' rootCount[i].Value == 3
 
      fixRootCount(i)
 
</code>
 
  
 
===Удаление дерева из кучи===
 
===Удаление дерева из кучи===
 
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>i</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
 
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>i</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
<code>
+
'''void''' delete('''int''' i, '''Node''' p):
  Delete(i, p)
+
  deleteTree(i, p)
    DeleteTree(i, p)
+
  rootCount[i].Value = rootCount[i].Value - 1
    RootCount[i].Value = RootCount[i].Value - 1
 
</code>
 
 
 
===Нахождение дерева с минимальным ключом в корне (<tex>MinKey()</tex>)===
 
  
<code>
+
===Нахождение дерева с минимальным ключом в корне <tex>\mathrm{minKey()}</tex>===
  MinKey()
+
'''Node''' minKey()
    MinP = NULL
+
  minP = NULL
    '''for''' i = 0 to MaxRank:
+
  '''for''' i = 0 to maxRank:
      p1 = MinKeyNodeRoot(RootCount[i].ListPointer)
+
    p1 = minKeyNodeRoot(rootCount[i].listPointer)
      '''if''' GetKey(p1) < GetKey(MinP):
+
    '''if''' getKey(p1) < getKey(minP):
        MinP = p1
+
      minP = p1
    '''return''' MinP
+
  '''return''' minP
</code>
 
  
 
==Счетчик нарушений==
 
==Счетчик нарушений==
Строка 347: Строка 329:
  
 
'''Счетчик нарушений''' представлен [[Саморасширяющийся массив|саморасширяющимся массивом]], элементы которого состоят из четырех полей:
 
'''Счетчик нарушений''' представлен [[Саморасширяющийся массив|саморасширяющимся массивом]], элементы которого состоят из четырех полей:
*<tex>CountViolation[i].Value</tex> {{---}} количество неправильных узлов ранга <tex>i</tex> в куче.
+
*<tex>\mathtt{countViolation[i].Value}</tex> {{---}} количество неправильных узлов ранга <tex>i</tex> в куче.
*<tex>CountViolation[i].ForvardPointer</tex> {{---}} прямой указатель <tex>i</tex>-го разряда
+
*<tex>\mathtt{countViolation[i].forvardPointer}</tex> {{---}} прямой указатель <tex>i</tex>-го разряда
*<tex>CountViolation[i].FirstViolation</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>
+
*<tex>\mathtt{countViolation[i].firstViolation}</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>
*<tex>CountViolation[i].SecondViolation</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>
+
*<tex>\mathtt{countViolation[i].secondViolation}</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>
 
 
  
 
{{Утверждение
 
{{Утверждение
Строка 365: Строка 346:
 
}}
 
}}
  
Для '''инициализации''' нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга <tex>MaxRank + 1</tex>. Это первый момент появления в куче узла ранга <tex>MaxRank + 1</tex>. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного <tex>MaxRank + 1</tex>, соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
+
Для '''инициализации''' нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга <tex>\mathtt{maxRank + 1}</tex>. Это первый момент появления в куче узла ранга <tex>\mathtt{maxRank + 1}</tex>. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного <tex>\mathtt{maxRank + 1}</tex>, соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
  
=Основные операции=
+
==Основные операции==
* <tex>MakeHeap</tex> {{---}}<tex>O(1)</tex>
+
Рассмотрим операции, которые можно производить с толстой кучей. Время работы основных операций указано в таблице:
заключается в инициализации счетчиков.
+
{| class="wikitable" style="width:10cm" border=1
* <tex>FindMin</tex> {{---}}<tex>O(1)</tex>
+
|+
возвращает указатель на минимальный элемент.
+
|-align="center" bgcolor=#EEEEFF
* <tex>Insert(key)</tex> {{---}} <tex>O(1)</tex>
+
! Операция || Время работы
 +
|-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> в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
* <tex>DecreaseKey</tex> {{---}} <tex>O(1)</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>  счетчика нарушений.
* <tex>DeleteMin</tex> {{---}} <tex>O(\log(n))</tex>
+
 
 +
===deleteMin===
 
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.  
 
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.  
 
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
 
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
* <tex>Delete</tex> {{---}} <tex>O(\log(n))</tex>
 
выполняем <tex>DecreaseKey</tex> а затем <tex>DeleteMin</tex>
 
* <tex>Meld(h1, h2)</tex> {{---}} <tex>O(\log(n))</tex>
 
Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — <tex>р2</tex> . Пройти по счетчику нарушений <tex>p2</tex>  от младшей цифры к старшей, пропуская цифры со значением <tex>0</tex> . Для  <tex>i</tex>-й цифры  <tex>d_i != 0</tex> делаем операцию фиксирования на каждой цифре, показываемой прямым указателем <tex>d_i</tex> , если эта цифра имеет значение 2. Затем, если <tex>d_i = 2</tex> , фиксируем <tex>d_i</tex> . Если <tex>d_i = 1</tex> , преобразуем это  <tex>i</tex>-ранговое нарушение в  <tex>(i+1)</tex>-ранговое нарушение, как при фиксировании, используя  <tex>i</tex>-рангового брата нарушенного узла вместо (несуществующего) другого  <tex>i</tex> -рангового нарушения.
 
Как только <tex>h2</tex>  не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика <tex>h2</tex>  в корневой счетчик <tex>h1</tex> инкрементированием соответствующих цифр. Если минимальный узел  <tex>h2</tex> содержит меньший ключ, чем минимальный узел <tex>h1</tex> , следует установить новым минимальным узлом  <tex>h1</tex> минимальный узел <tex>h2</tex> . Затем нужно вернуть модифицированную кучу <tex>h1</tex>  в качестве результата <tex>Meld</tex> .
 
* <tex>DeleteViolation</tex>
 
для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
 
  
<code>
+
===delete===
   DeleteViolation(h2)
+
Выполняем <tex>\mathrm{decreaseKey}</tex> а затем <tex>\mathrm{deleteMin}</tex>.
    '''for''' i = 0 '''to''' h2.MaxRank:
+
 
    '''if''' CountViolation[i].Value == 2:
+
===meld(h1, h2)===
      FixCountViolation(i)
+
Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — <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> -рангового нарушения.
    '''for''' i = 0 to h2.MaxRank:
+
Как только <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> .
      '''if''' CountViolation[i].Value == 1:
+
        IncCountViolation(i, SearchBrother(CountViolation[i].rmFirstviolation))
+
===deleteViolation===
        FixCountViolation(i)
+
Для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
</code>
+
'''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/1543?page=1 Толстые кучи  — INTUIT.ru]
+
* [http://www.intuit.ru/studies/courses/100/100/lecture/2935?page=1 INTUIT.ru {{---}} Толстые кучи]
* [http://compscicenter.ru/program/lecture/6829 приоритетные очереди - CS center]
+
* [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

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

Определение:
Определяем толстое дерево (англ. Thick tree) [math]F_k[/math] ранга [math]k ~(k = 0, 1, 2 ,\ldots )[/math] следующим образом:
  • Толстое дерево [math]F_0[/math] ранга ноль состоит из единственного узла.
  • Толстое дерево [math]F_k[/math] ранга [math]k[/math], для [math]k = 1, 2, 3,\ldots [/math], состоит из трех деревьев [math]F_{k-1}[/math] ранга [math]k-1[/math],таких, что корни двух из них являются самыми левыми потомками корня третьего.
Пример толстых деревьев [math]F_0, F_1, F_2, F_3[/math]


Определение:
Ранг узла [math]x[/math] в толстом дереве определяется как ранг толстого поддерева с корнем в узле [math]x[/math].


Свойства толстых деревьев

Утверждение:
В толстом дереве ранга [math]k[/math] ровно [math]3^k[/math] узлов.
Определение:
Толстый лес (англ. Thick forest) — это набор толстых деревьев, ранги которых не обязательно попарно различны.


Утверждение:
Для любого натурального числа [math]n[/math] существует лес из толстых деревьев, в котором ровно [math]n[/math] узлов.
[math]\triangleright[/math]
Действительно, такой лес можно построить, включив в него столько деревьев ранга [math]i[/math], каково значение [math]i[/math]-го разряда представления числа [math]n[/math] в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
[math]\triangleleft[/math]
Утверждение:
Толстый лес из [math]n[/math] узлов содержит [math]O(n\log{n})[/math] деревьев.

Толстые кучи

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


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


Определение:
Нагруженный лес назовем почти кучеобразным, если для каждого значения [math]k[/math] в нем имеется не более двух неправильных узлов ранга [math]k[/math].

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

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


Структура узла

Каждый узел толстой кучи будем представлять записью со следующими полями:

struct Node
  int key       // ключ элемента, приписанного узлу дерева
  Node parent   // указатель на родителя узла
  Node left     // указатель на ближайшего левого брата узла
  Node right    // указатель на ближайшего правого брата узла
  Node lChild   // указатель на самого левого сына
  int rank      // ранг узла

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

Структура кучи

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

struct FatHeap
  int[] rootCount        // массив, соответствующий корневому счетчику
  int[] countViolation   // массив, соответствующий счетчику нарушений
  Node minPointer        // указатель на элемент кучи с минимальным ключом
  int maxRank            // наибольший ранг среди рангов деревьев, присутствующих в куче
Представление леса списком

Избыточное представление чисел

Определение:
Избыточным [math]b[/math]-арным представлением числа [math]x[/math] будем называть последовательность [math]d = d_n, d_{n-1}, \ldots, d_0[/math], такую что

[math]x = {\sum\limits^{n}_{i = 0} {d_i}}{b^i}[/math]

где [math] d_i \in \{0, 1, \ldots, b\} [/math], [math] i \in \{0, 1, \ldots, n\} [/math]


Определение:
Назовем [math]b[/math]-арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами, равными [math]b[/math] , найдется цифра, отличная от [math]b-1[/math].


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


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

  • [math]L'(i) = L(i)[/math] , если [math]d_i \in \{b-1, b-2\}[/math] и [math]d(L(i))=b[/math];
  • [math]L'(i)[/math] — произвольное число [math]\gt i[/math], если [math]d_i \in \{b-1, b-2\}[/math] и [math]d(L(i))\lt b-1[/math];
  • [math]L'(i)[/math] — не определено, если [math]d \notin \{b-1, b-2 \}[/math] .


Фиксация цифры

Фиксацией цифры [math]b[/math], стоящей в [math]i[/math]-м разряде представления [math]d[/math], назовем операцию [math]\mathrm{fix(i)}[/math], заключающуюся в обнулении цифры [math]d_i[/math] и инкрементировании цифры [math] d_{i+1} [/math], при этом если [math]i=n[/math] , то полагаем [math]d_{i+1} = 1[/math]. При каждом выполнении операции фиксации будем обновлять значение [math]L'(i)[/math]. Очевидно, при [math]b\gt 2[/math] операцию [math]\mathrm{fix(i)}[/math] можно выполнить следующим образом:

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

Инкремент

Операцию [math]\mathrm{inc(i)}[/math] инкрементирования [math]i[/math]-й цифры избыточного представления [math]d[/math] можно выполнить так:

void inc(int i):
  fix(i)
  if (d[i] == b - 1) or (d[i] == b - 2)
    fix(L'[i])
  d[i]++
  fix(i)

Декремент

Эта схема может быть расширена для выполнения за константное время декрементирования произвольной цифры добавлением дополнительного цифрового значения [math]b+1[/math].

Представление приоритетной очереди основано на использовании так называемых избыточных счетчиков, позволяющих за время [math]O(1)[/math] инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь один из способов реализации толстых куч. На самом деле, для их реализации подойдет произвольный d-арный счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.

Корневой счетчик

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

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

Утверждение (о корневом счетчике):
Из определения корневого счетчика следует:
  • Корневой счетчик позволяет иметь доступ к корню любого дерева ранга [math]i[/math] за время [math]O(1)[/math].
  • Вставка толстого дерева ранга [math]i[/math] соответствует операции инкрементирования [math]i[/math]-го разряда корневого счетчика.
  • Удаление толстого поддерева ранга [math]i[/math] соответствует операции декрементирования [math]i[/math]-го разряда корневого счетчика.
  • Операции инкрементирования и декрементирования [math]i[/math]-го разряда корневого счетчика осуществляются за время [math]O(1)[/math].

Корневой счетчик представляем расширяющимся массивом [math]\mathtt{rootCount}[/math] , каждый элемент которого — запись с тремя полями:

  • [math]\mathtt{rootCount[i].Value}[/math][math]i[/math]-й разряд равный количеству деревьев ранга [math]i[/math].
  • [math]\mathtt{rootCount[i].forwardPointer}[/math] — прямой указатель [math]i[/math]-го разряда.
  • [math]\mathtt{rootCount[i].listPointer}[/math] — указатель на список деревьев ранга [math]i[/math], присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя [math]Right[/math] корневых узлов связываемых деревьев. Если в куче нет деревьев ранга [math]i[/math] , то указатель [math]\mathtt{listPointer}[/math] равен [math]NULL[/math].

Заметим, что если значение равно нулю, то нам неважно значение указателя [math]\mathtt{rootCount[i].listPointer}[/math].

Инициализация

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

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

Обновление прямого указателя

Обновление прямого указателя [math]i[/math]-го разряда корневого счетчика заключается в выполнении следующего псевдокода:

void updateForwardPionter(int i):
  if rootCount[i + 1].Value == 3 - 1
    rootCount[i].forwardPointer = rootCount[i + 1].forwardPointer
  else
    rootCount[i].forwardPointer = i + 1

Корректировка при вставке

Корректировка списочной части [math]i[/math]-го разряда корневого счетчика при вставке в кучу нового дерева ранга [math]i~(\mathrm{insertTree(i,p)})[/math]. Эта процедура вставляет новое дерево ранга [math]i[/math] (на него указывает указатель [math]p[/math]) в списочную часть [math]i[/math]-го разряда корневого счетчика [math]\mathtt{rootCount}[/math] выглядит так:

void insertTree(int i, Node p):
  p1 = rootCount[i].listPointer
  if rootCount[i].Value [math] \ne [/math] 0
    p.right = p1
  else
    p.right = NULL
  p.left = NULL
  rootCount[i].listPointer = p

Корректировка при удалении

Корректировка списочной части [math]i[/math]-го разряда корневого счетчика при удалении из кучи дерева ранга [math]i~(\mathrm{deleteTree(i,p)})[/math]. Эта процедура удаляет дерево ранга [math]i[/math] (на него указывает указатель [math]p[/math]) из списочной части [math]i[/math]-го разряда корневого счетчика [math]\mathtt{rootCount}[/math] . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:

void deleteTree(int i, Node p):
  p1 = rootCount[i].listPointer
  if p1 == p
    rootCount[i].listPointer = p.right
  j = 1
  while (j [math] \leqslant [/math] rootCount[i].Value) and (p1.right [math] \ne [/math] p):
    j++
    p1 = p1.right
  p1.right = p.right

Связывание трех деревьев в одно

Связывание [math]\mathrm{fastening (p1, p2, p3)}[/math] трех толстых деревьев ранга [math]i[/math] в одно толстое дерево ранга [math]i+1[/math]. Эта функция принимает три указателя [math]p1, p2 ,p3[/math] на три разных толстых дерева одного и того же ранга [math]i[/math] и возвращает указатель на вновь сформированное дерево ранга [math]i+1[/math] . Процедура заключается в выполнении следующего псевдокода:

Node fastening(Node p1, Node p2, Node p3):
  if (p1.key [math] \leqslant [/math] p2.key) and (p1.Key [math] \leqslant [/math] p3.key)
    minP = p1
    p1 = p2
    p2 = p3
  if (p2.key [math] \leqslant [/math] p1.key) and (p2.key [math] \leqslant [/math] p3.key)
    minP = p2
    p1 = p1
    p2 = p3
  if (p3.key [math] \leqslant [/math] p1.key) and (p3.key [math] \leqslant [/math] 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 [math] \ne [/math] NULL
    minP.lChild.left = p2
  minP.lChild = p1
  minP.rank = minP.rank + 1
  minP.right = NULL
  minP.left = NULL
  return minP

Значение ключа элемента по указателю

Функция [math]\mathrm{getKey(p)}[/math] по указателю p на элемент определяет значение его ключа:

//под [math]\infty[/math] нужно понимать нейтральный относительно минимума элемент.
int getKey(Node p):
  if p == NULL
    min = [math]\infty[/math]
  else
    min = p.key
  return min

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

Функция [math]\mathrm{minKeyNodeRoot(p)}[/math], которая по указателю [math]p[/math] на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:

Node minKeyNodeRoot(Node p):
  p1 = p
  minP = p1
  while p1 [math] \ne [/math] NULL
    if p1.key < minP.key
      minP = p1
      p1 = p1.right
  return minP

Операция фиксации

Операция фиксации [math]\mathrm{rmFixRootCount(i)}[/math] для [math]i[/math]-го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга [math]i[/math], состоящий ровно из трех деревьев. При выполнении этой операции значение в [math]i[/math]-м разряде — должно стать равным нулю, а значение в [math]i[/math]-м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга [math]i[/math], а количество деревьев ранга [math]i+1[/math] должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга [math]i[/math] , связать их в дерево ранга [math]i+1[/math] и вставить вновь полученное дерево в кучу. Следует учесть, что ранг нового дерева может стать больше, чем [math]\mathtt{maxRank}[/math], что потребует инициализации нового разряда. Для этого необходимо увеличить значение [math]\mathtt{maxRank}[/math] на единицу и заполнить новое поле, а также провести инициализацию нового разряда.

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-го разряда корневого счетчика

По сравнению с описанным алгоритмом инкрементирования [math]i[/math]-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.

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)

Удаление дерева из кучи

Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг [math]i[/math] . Тогда значение [math]i[/math]-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.

void delete(int i, Node p):
  deleteTree(i, p)
  rootCount[i].Value = rootCount[i].Value - 1

Нахождение дерева с минимальным ключом в корне [math]\mathrm{minKey()}[/math]

Node minKey()
  minP = NULL
  for i = 0 to maxRank:
    p1 = minKeyNodeRoot(rootCount[i].listPointer)
    if getKey(p1) < getKey(minP):
      minP = p1
  return minP

Счетчик нарушений

Заметим, что счетчик нарушений очень похож на корневой счетчик выше, но в отличие от второго:

  • Нас теперь интересует не само число, а только значения разрядов.
  • Операция фиксации тесно связана с толстой кучей.

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

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

Счетчик нарушений представлен саморасширяющимся массивом, элементы которого состоят из четырех полей:

  • [math]\mathtt{countViolation[i].Value}[/math] — количество неправильных узлов ранга [math]i[/math] в куче.
  • [math]\mathtt{countViolation[i].forvardPointer}[/math] — прямой указатель [math]i[/math]-го разряда
  • [math]\mathtt{countViolation[i].firstViolation}[/math] — указатель на неправильный узел ранга [math]i[/math]
  • [math]\mathtt{countViolation[i].secondViolation}[/math] — указатель на неправильный узел ранга [math]i[/math]
Утверждение (о счетчике нарушений):
из определения счетчика нарушений следует:
  • Наличие счетчика нарушений позволяет иметь доступ к любому неправильному узлу ранга [math]i[/math] за время [math]O(1)[/math] .
  • Уменьшение ключа у элемента ранга [math]i[/math] соответствует операции инкрементирования [math]i[/math]-го разряда счетчика нарушений (естественно, лишь в случае, когда новое значение ключа у изменяемого узла становится меньше значения ключа его родителя).
  • Операции инкрементирования и декрементирования [math]i[/math]-го разряда осуществляются за время [math]O(1)[/math].

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

Основные операции

Рассмотрим операции, которые можно производить с толстой кучей. Время работы основных операций указано в таблице:

Операция Время работы
[math]\mathrm{makeHeap}[/math] [math]O(1)[/math]
[math]\mathrm{findMin}[/math] [math]O(1)[/math]
[math]\mathrm{insert(key)}[/math] [math]O(1)[/math]
[math]\mathrm{decreaseKey}[/math] [math]O(1)[/math]
[math]\mathrm{deleteMin}[/math] [math]O(\log(n))[/math]
[math]\mathrm{delete}[/math] [math]O(\log(n))[/math]
[math]\mathrm{meld(h1, h2)}[/math] [math]O(\log(n))[/math]

makeHeap

Заключается в инициализации счетчиков.

findMin

Возвращает указатель на минимальный элемент.

insert(key)

Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга [math]0[/math] в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.

decreaseKey

Чтобы выполнить эту операцию, поступим следующим образом. Пусть [math]x[/math] — узел, на который указывает указатель [math]p[/math] . Вычитаем [math]\delta[/math] из ключа узла [math]x[/math] . Если новый ключ [math]x[/math] меньше минимального ключа кучи [math]H[/math], обмениваем ключ элемента [math]p[/math] с ключом минимального элемента. Новых нарушений операция не создаст. Пусть [math]r[/math] — ранг [math]x[/math] . Если [math]x[/math] — нарушаемый узел, добавляем [math]x[/math] как новое [math]r[/math]-ранговое нарушение инкрементированием [math]r[/math]-й цифры [math]d_r[/math] счетчика нарушений.

deleteMin

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

delete

Выполняем [math]\mathrm{decreaseKey}[/math] а затем [math]\mathrm{deleteMin}[/math].

meld(h1, h2)

Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — [math]р2[/math] . Пройти по счетчику нарушений [math]p2[/math] от младшей цифры к старшей, пропуская цифры со значением [math]0[/math] . Для [math]i[/math]-й цифры [math]d_i != 0[/math] делаем операцию фиксирования на каждой цифре, показываемой прямым указателем [math]d_i[/math] , если эта цифра имеет значение [math]2[/math]. Затем, если [math]d_i = 2[/math] , фиксируем [math]d_i[/math] . Если [math]d_i = 1[/math] , преобразуем это [math]i[/math]-ранговое нарушение в [math](i+1)[/math]-ранговое нарушение, как при фиксировании, используя [math]i[/math]-рангового брата нарушенного узла вместо (несуществующего) другого [math]i[/math] -рангового нарушения. Как только [math]h2[/math] не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика [math]h2[/math] в корневой счетчик [math]h1[/math] инкрементированием соответствующих цифр. Если минимальный узел [math]h2[/math] содержит меньший ключ, чем минимальный узел [math]h1[/math] , следует установить новым минимальным узлом [math]h1[/math] минимальный узел [math]h2[/math] . Затем нужно вернуть модифицированную кучу [math]h1[/math] в качестве результата [math]\mathrm{meld}[/math] .

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)

См. также

Источники информации