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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Счетчик нарушений)
(Основные операции)
Строка 368: Строка 368:
  
 
=Основные операции=
 
=Основные операции=
* <tex>MakeHeap</tex> {{---}}<tex>O(1)</tex>
+
* <tex>makeHeap</tex> {{---}}<tex>O(1)</tex>
 
заключается в инициализации счетчиков.  
 
заключается в инициализации счетчиков.  
* <tex>FindMin</tex> {{---}}<tex>O(1)</tex>
+
* <tex>findMin</tex> {{---}}<tex>O(1)</tex>
 
возвращает указатель на минимальный элемент.  
 
возвращает указатель на минимальный элемент.  
* <tex>Insert(key)</tex> {{---}} <tex>O(1)</tex>
+
* <tex>insert(key)</tex> {{---}} <tex>O(1)</tex>
 
Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга <tex>0</tex> в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
 
Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга <tex>0</tex> в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
* <tex>DecreaseKey</tex> {{---}} <tex>O(1)</tex>
+
* <tex>decreaseKey</tex> {{---}} <tex>O(1)</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>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>
+
* <tex>deleteMin</tex> {{---}} <tex>O(\log(n))</tex>
 
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.  
 
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.  
 
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
 
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
* <tex>Delete</tex> {{---}} <tex>O(\log(n))</tex>
+
* <tex>delete</tex> {{---}} <tex>O(\log(n))</tex>
выполняем <tex>DecreaseKey</tex> а затем <tex>DeleteMin</tex>
+
выполняем <tex>decreaseKey</tex> а затем <tex>deleteMin</tex>
* <tex>Meld(h1, h2)</tex> {{---}} <tex>O(\log(n))</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>р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>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>
+
* <tex>deleteViolation</tex>
 
для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
 
для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
  
 
<code>
 
<code>
   DeleteViolation(h2)
+
   deleteViolation(h2):
     '''for''' i = 0 '''to''' h2.MaxRank:
+
     '''for''' i = 0 '''to''' h2.maxRank
     '''if''' CountViolation[i].Value == 2:
+
     '''if''' countViolation[i].Value == 2
       FixCountViolation(i)
+
       fixCountViolation(i)
     '''for''' i = 0 to h2.MaxRank:
+
     '''for''' i = 0 to h2.maxRank
       '''if''' CountViolation[i].Value == 1:
+
       '''if''' countViolation[i].Value == 1
         IncCountViolation(i, SearchBrother(CountViolation[i].rmFirstviolation))
+
         incCountViolation(i, searchBrother(countViolation[i].rmFirstviolation))
         FixCountViolation(i)
+
         fixCountViolation(i)
 
</code>
 
</code>
  

Версия 22:46, 7 июня 2015

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

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


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


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


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


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


Толстые кучи

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


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


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

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

  • [math]key[/math] — ключ элемента, приписанного узлу дерева
  • [math]parent[/math] — указатель на родителя
  • [math]left[/math] — указатель на ближайшего левого брата
  • [math]right[/math] — указатель на ближайшего правого брата
  • [math]lChild[/math] — указатель на самого левого сына
  • [math]rank[/math] — ранг узла.

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

Представление леса списком

Вспомогательные структуры

Нам понадобятся понятия корневого счетчика и счетчика нарушений.

Толстую кучу будем представлять записью следующего вида: [math]fatHeap = (rootCount, countViolation, minpointer, maxRank)[/math], где:

[math]rootCount[/math] — массив, соответствующий корневому счетчику

[math]countViolation[/math] — массив, соответствующий счетчику нарушений

[math]minPointer[/math] — указатель на элемент кучи с минимальным ключом

[math]maxRank[/math]наибольший ранг среди рангов деревьев, присутствующих в куче

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

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

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

где [math] d_i \in \{0, 1, ..., b\} [/math], [math] i \in \{0, 1, ..., 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, ... 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]L'(i)[/math] будем называть прямым указателем.


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

Фиксацией цифры [math]b[/math], стоящей в [math]i[/math]-м разряде представления [math]d[/math], (fix(i)) назовем операцию, заключающуюся в обнулении цифры [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]fix(i)[/math] можно выполнить следующим образом:

   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]i[/math]-й цифры избыточного представления [math]d[/math] [math]inc(i)[/math] можно выполнить так:

 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]rootCount[/math] , каждый элемент которого — запись с тремя полями:

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

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

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

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

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

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

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

  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~(insertTree(i,p))[/math]. Эта процедура вставляет новое дерево ранга [math]i[/math] (на него указывает указатель [math]p[/math]) в списочную часть [math]i[/math]-го разряда корневого счетчика [math]rootCount[/math] выглядит так:

 insertTree(i, 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~(deleteTree(i,p))[/math]. Эта процедура удаляет дерево ранга [math]i[/math] (на него указывает указатель [math]p[/math]) из списочной части [math]i[/math]-го разряда корневого счетчика [math]rootCount[/math] . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:

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

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

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

 fastening (p1, p2, p3):
   if (p1.key [math] \le [/math] p2.key) and (p1.Key [math] \le [/math] p3.key)
     minP = p1
     p1 = p2
     p2 = p3
   if (p2.key [math] \le [/math] p1.key) and (p2.key [math] \le [/math] p3.key)
     minP = p2
     p1 = p1
     p2 = p3
   if (p3.key [math] \le [/math] p1.key) and (p3.key [math] \le [/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]getKey(p)[/math] по указателю p на элемент определяет значение его ключа:

// под [math]\infty[/math] нужно понимать нейтральный относительно минимума элемент.

 getKey(p):
   if p == NULL
     min = [math]\infty[/math]
   else
     min = p.key
   return min 

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

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

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

Операция фиксации [math]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]maxRank[/math], что потребует инициализации нового разряда. Для этого необходимо увеличить значение [math]maxRank[/math] на единицу и заполнить новое поле, а также провести инициализацию нового разряда.

 rmFixRootCount(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]-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.

 rmIncRootCount(i,p)
   if (rootCount[i].Value == 1) or (rootCount[i].Value == 2)
     if rootCount[rootCount[i].forwardPointer].Value == 3
       fixRootCount(rootCount[i].forwardPointer);
   if rootCount[i].Value == 3
     fixRootCount(i)
   insertTree(i, p)
   rootCount[i].Value = rootCount[i].Value + 1
   updateForwardPointer(i)
   if rootCount[i].Value == 3
     fixRootCount(i)

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

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

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

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

 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]countViolation[i].Value[/math] — количество неправильных узлов ранга [math]i[/math] в куче.
  • [math]countViolation[i].forvardPointer[/math] — прямой указатель [math]i[/math]-го разряда
  • [math]countViolation[i].firstViolation[/math] — указатель на неправильный узел ранга [math]i[/math]
  • [math]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]maxRank + 1[/math]. Это первый момент появления в куче узла ранга [math]maxRank + 1[/math]. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного [math]maxRank + 1[/math], соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.

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

  • [math]makeHeap[/math][math]O(1)[/math]

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

  • [math]findMin[/math][math]O(1)[/math]

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

  • [math]insert(key)[/math][math]O(1)[/math]

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

  • [math]decreaseKey[/math][math]O(1)[/math]

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

  • [math]deleteMin[/math][math]O(\log(n))[/math]

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

  • [math]delete[/math][math]O(\log(n))[/math]

выполняем [math]decreaseKey[/math] а затем [math]deleteMin[/math]

  • [math]meld(h1, h2)[/math][math]O(\log(n))[/math]

Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — [math]р2[/math] . Пройти по счетчику нарушений [math]p2[/math] от младшей цифры к старшей, пропуская цифры со значением [math]0[/math] . Для [math]i[/math]-й цифры [math]d_i != 0[/math] делаем операцию фиксирования на каждой цифре, показываемой прямым указателем [math]d_i[/math] , если эта цифра имеет значение 2. Затем, если [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]meld[/math] .

  • [math]deleteViolation[/math]

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

 deleteViolation(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)

Источники