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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Основные операции)
Строка 84: Строка 84:
 
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
 
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
 
* <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>

Версия 00:18, 22 мая 2013

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

Определение:
Определяем толстое дерево [math]F_k[/math] ранга [math]k[/math] [math]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].


//[[Файл:ThickTreeExample.gif Пример толстых деревьев [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] деревьев.


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


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


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


Толстые кучи

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


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

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

  • [math]Key[/math] — ключ элемента, приписанного узлу дерева
  • [math]Parent[/math] — указатель на родителя
  • [math]Lest[/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].

//[[Файл:ThickTreeExample.gif Пример толстых деревьев [math]F_0, F_1, F_2, F_3[/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]