Толстая куча на избыточном счётчике — различия между версиями
Slavian (обсуждение | вклад) |
(→Толстое дерево) |
||
Строка 5: | Строка 5: | ||
|neat = 1 | |neat = 1 | ||
|definition= | |definition= | ||
− | Определяем '''толстое дерево''' <tex>F_k</tex> ранга <tex>k ~(k = 0, 1, 2 ~\dots )</tex> следующим образом: | + | Определяем '''толстое дерево''' (англ. ''Fat Heap'') <tex>F_k</tex> ранга <tex>k ~(k = 0, 1, 2 ~\dots )</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,\dots </tex>, состоит из трех деревьев <tex>F_{k-1}</tex> ранга <tex>k</tex>,таких, что корни двух из них являются самыми левыми потомками корня третьего. | ||
Строка 35: | Строка 35: | ||
|neat = | |neat = | ||
|definition= | |definition= | ||
− | '''Узел''' в ''нагруженном лесе'' назовем '''неправильным''', если его ключ меньше ключа его родителя. | + | '''Узел''' (англ. ''Node'') в ''нагруженном лесе'' назовем '''неправильным''', если его ключ меньше ключа его родителя. |
}} | }} | ||
{{Определение | {{Определение |
Версия 21:32, 7 июня 2015
Содержание
- 1 Толстое дерево
- 2 Толстые кучи
- 3 Вспомогательные структуры
- 3.1 Избыточное представление чисел
- 3.2 Корневой счетчик
- 3.2.1 Инициализация
- 3.2.2 Обновление прямого указателя
- 3.2.3 Корректировка при вставке
- 3.2.4 Корректировка при удалении
- 3.2.5 Связывание трех деревьев в одно
- 3.2.6 Значение ключа элемента по указателю
- 3.2.7 Узел с минимальным ключом
- 3.2.8 Операция фиксации [math]rmFixRootCount(i)[/math]
- 3.2.9 Инкрементирование i-го разряда корневого счетчика
- 3.2.10 удаление дерева из кучи
- 3.2.11 Нахождение дерева с минимальным ключом в корне ([math]MinKey()[/math])
- 3.3 Счетчик нарушений
- 4 Основные операции
- 5 Источники
Толстое дерево
- Толстое дерево
- Толстое дерево ранга , для , состоит из трех деревьев ранга ,таких, что корни двух из них являются самыми левыми потомками корня третьего.
Утверждение: |
Свойства толстых деревьев:
|
Определение: |
Лес будем называть нагруженным, если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества. |
Определение: |
Узел (англ. Node) в нагруженном лесе назовем неправильным, если его ключ меньше ключа его родителя. |
Определение: |
Нагруженный лес назовем почти кучеобразным, если для каждого значения | в нем имеется не более двух неправильных узлов ранга .
Толстые кучи
здесь и далее "Толстая куча на избыточном счетчике" будет заменено на более лаконичное "Толстая куча".
Определение: |
Толстая куча — это почти кучеобразный нагруженный лес. |
Представление толстой кучи
Каждый узел толстой кучи будем представлять записью со следующими полями:
- — ключ элемента, приписанного узлу дерева
- — указатель на родителя
- — указатель на ближайшего левого брата
- — указатель на ближайшего правого брата
- — указатель на самого левого сына
- — ранг узла.
"Братья" (узлы корневых деревьев, а также сыновья каждого узла) объединены в двусвязный список при помощи указателей
и . У самого левого (правого) "брата" в этом списке указатель ( ) равен .Вспомогательные структуры
Нам понадобятся понятия корневого счетчика и счетчика нарушений.
Толстую кучу будем представлять записью следующего вида:
, где:— массив, соответствующий корневому счетчику
— массив, соответствующий счетчику нарушений
— указатель на элемент кучи с минимальным ключом
— наибольший ранг среди рангов деревьев, присутствующих в куче
Избыточное представление чисел
Определение: |
Избыточным где , | -арным представлением числа будем называть последовательность , такую что
Определение: |
Назовем | -арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами, равными , найдется цифра, отличная от .
Определение: |
Пусть
| — номер разряда, отличного от и ближайшего слева от -го разряда в регулярном -арном избыточном представлении .
фиксация цифры
Фиксацией цифры
Fix(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
инкремент
Инкрементирование
Inc(i) Fix(i) if (d[i] == b - 1) or (d[i] == b - 2): Fix(L'[i]) d[i]++ Fix(i)
декремент
Эта схема может быть расширена для выполнения за константное время декрементирования произвольной цифры добавлением дополнительного цифрового значения
.
Представление приоритетной очереди основано на использовании так называемых избыточных счетчиков, позволяющих за время
инкрементировать любой разряд. Заметим, что использованные здесь счетчики — лишь один из способов реализации толстых куч. На самом деле, для их реализации подойдет произвольный d-арный счетчик, при условии, что трудоемкость инкрементирования любого его разряда является константной.
Корневой счетчик
Корневой счетчик состоит из избыточного троичного представления числа элементов в куче и набора списочных элементов.
Значение его
-го разряда равно количеству деревьев ранга , присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга содержит ровно узлов. Заметим, что состояние избыточного корневого представления определяется неоднозначно. Очевидно, что для любой толстой кучи, состоящей из элементов, существует регулярное избыточное представление корневого счетчика. Списочный элемент, приписанный -му разряду избыточного корневого представления, — это указатель на список деревьев ранга , присутствующих в куче, образованный посредством указателей корневых узлов связываемых деревьев.Утверждение (о корневом счетчике): |
Из определения корневого счетчика следует:
|
Корневой счетчик представляем расширяющимся массивом
, каждый элемент которого — запись с тремя полями:- — -й разряд равный количеству деревьев ранга .
- — прямой указатель -го разряда.
- — указатель на список деревьев ранга , присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя корневых узлов связываемых деревьев. Если в куче нет деревьев ранга , то указатель равен .
Заметим, что если значение равно нулю, то нам неважно значение указателя
.Инициализация
Чтобы время инициализации счетчиков было
, используем поразрядную их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную , которая показывает нам, какая часть массивов счетчиков используется в данный момент.При начальной инициализации необходимо установить счетчики в состояние, которое отвечает пустой куче. Очевидно, что в пустой куче не может быть никаких нарушений.
Обновление прямого указателя
Обновление прямого указателя
UpdateForwardPionter(i) if RootCount[i + 1].Value == 3 - 1: RootCount[i].ForwardPointer = RootCount[i + 1].ForwardPointer else: RootCount[i].ForwardPointer = i + 1
Корректировка при вставке
Корректировка списочной части
-го разряда корневого счетчика при вставке в кучу нового дерева ранга . Эта процедура вставляет новое дерево ранга (на него указывает указатель ) в списочную часть -го разряда корневого счетчика выглядит так:
InsertTree(i, p)
p1 = RootCount[i].ListPointer
if RootCount[i].Value
0:
p.Right = p1
else:
p.Right = NULL
p.Left = NULL
RootCount[i].ListPointer = p
Корректировка при удалении
Корректировка списочной части
-го разряда корневого счетчика при удалении из кучи дерева ранга . Эта процедура удаляет дерево ранга (на него указывает указатель ) из списочной части -го разряда корневого счетчика . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:
DeleteTree(i, p) p1 = RootCount[i].ListPointer if p1 == p: RootCount[i].ListPointer = p.Right j = 1 while (jRootCount[i].Value) and (p1.Right p): j++ p1 = p1.Right p1.Right = p.Right
Связывание трех деревьев в одно
Связывание
трех толстых деревьев ранга в одно толстое дерево ранга . Эта функция принимает три указателя на три разных толстых дерева одного и того же ранга и возвращает указатель на вновь сформированное дерево ранга . Процедура заключается в выполнении следующего псевдокода:
Fastening (p1, p2, p3) if (p1.Keyp2.Key) and (p1.Key p3.Key): MinP = p1 p1 = p2 p2 = p3 if (p2.Key p1.Key) and (p2.Key p3.Key): MinP = p2 p1 = p1 p2 = p3 if (p3.Key p1.Key) and (p3.Key p2.Key) MinP = p3 p1 = p1 p2 = p2 p1.Right = p2 p1.Left = NULL p1.Parent = MinP p2.Right = MinP.LChild p2.Left = p1 p2.Parent = MinP if MinP.LChild NULL: MinP.LChild.Left = p2 MinP.LChild = p1 MinP.Rank = MinP.Rank + 1 MinP.Right = NULL MinP.Left = NULL return MinP
Значение ключа элемента по указателю
Функция
по указателю p на элемент определяет значение его ключа:// под
нужно понимать нейтральный относительно минимума элемент.
GetKey(p)
if p == NULL:
Min =
else:
Min = p.key
return Min
Узел с минимальным ключом
Функция
MinKeyNodeRoot(p)
p1 = p
MinP = p1
while p1
NULL:
if p1.Key < MinP.Key:
MinP = p1
p1 = p1.Right
return MinP
Операция фиксации
Операция фиксации
-го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга , состоящий ровно из трех деревьев. При выполнении этой операции значение в -м разряде — должно стать равным нулю, а значение в -м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга , а количество деревьев ранга должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга , связать их в дерево ранга и вставить вновь полученное дерево в кучу. Следует учесть, что ранг нового дерева может стать больше, чем , что потребует инициализации нового разряда. Для этого необходимо увеличить значение на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
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-го разряда корневого счетчика
По сравнению с описанным алгоритмом инкрементирования
-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
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)
удаление дерева из кучи
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг
Delete(i, p) DeleteTree(i, p) RootCount[i].Value = RootCount[i].Value - 1
Нахождение дерева с минимальным ключом в корне ( )
MinKey() MinP = NULL for i = 0 to MaxRank: p1 = MinKeyNodeRoot(RootCount[i].ListPointer) if GetKey(p1) < GetKey(MinP): MinP = p1 return MinP
Счетчик нарушений
Заметим, что счетчик нарушений очень похож на корневой счетчик выше, но в отличие от второго:
- Нас теперь интересует не само число, а только значения разрядов.
- Операция фиксации тесно связана с толстой кучей.
Значение
-го разряда для счетчика нарушений интерпретируется как количество неправильных узлов ранга , а его списочная часть — это указатели на неправильные узлы ранга .Счетчик нарушений состоит из расширенного избыточного двоичного представления и набора списочных элементов.
Счетчик нарушений представлен Саморасширяющимся массивом, элементы которого состоят из четырех полей:
- — количество неправильных узлов ранга в куче.
- — прямой указатель -го разряда
- — указатель на неправильный узел ранга
- — указатель на неправильный узел ранга
Утверждение (о счетчике нарушений): |
из определения счетчика нарушений следует:
|
Для инициализации нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга
. Это первый момент появления в куче узла ранга . Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного , соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.Основные операции
- —
заключается в инициализации счетчиков.
- —
возвращает указатель на минимальный элемент.
- —
Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга
в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.- —
Чтобы выполнить эту операцию, поступим следующим образом. Пусть
— узел, на который указывает указатель . Вычитаем из ключа узла . Если новый ключ меньше минимального ключа кучи , обмениваем ключ элемента с ключом минимального элемента. Новых нарушений операция не создаст. Пусть — ранг . Если — нарушаемый узел, добавляем как новое -ранговое нарушение инкрементированием -й цифры счетчика нарушений.- —
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов. Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
- —
выполняем
а затем- —
Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча —
. Пройти по счетчику нарушений от младшей цифры к старшей, пропуская цифры со значением . Для -й цифры делаем операцию фиксирования на каждой цифре, показываемой прямым указателем , если эта цифра имеет значение 2. Затем, если , фиксируем . Если , преобразуем это -ранговое нарушение в -ранговое нарушение, как при фиксировании, используя -рангового брата нарушенного узла вместо (несуществующего) другого -рангового нарушения. Как только не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика в корневой счетчик инкрементированием соответствующих цифр. Если минимальный узел содержит меньший ключ, чем минимальный узел , следует установить новым минимальным узлом минимальный узел . Затем нужно вернуть модифицированную кучу в качестве результата .для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
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)