Изменения

Перейти к: навигация, поиск

Толстая куча на избыточном счётчике

689 байт убрано, 23:52, 31 января 2019
м
Дмитрий Мурзин переименовал страницу Толстая куча на избыточном счетчике в Толстая куча на избыточном счётчике: Ёфикация
Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log{n})</tex> деревьев.
|proof=
}}
 
{{Определение
|id=def2
|neat =
|definition=
'''Лес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.
}}
{{Определение
|id=def3
|neat =
|definition=
'''Узел''' (англ. ''Node'') в ''нагруженном лесе'' назовем '''неправильным''', если его ключ меньше ключа его родителя.
}}
{{Определение
|id=def4
|neat =
|definition=
'''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</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, '''intNode''' p):
p1 = rootCount[i].listPointer
'''if''' rootCount[i].Value <tex> \ne </tex> 0
===Корректировка при удалении===
Корректировка списочной части <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, '''intNode''' p):
p1 = rootCount[i].listPointer
'''if''' p1 == p
rootCount[i].listPointer = p.right
j = 1
'''while''' (j <tex> \le leqslant </tex> rootCount[i].Value) '''and''' (p1.right <tex> \ne </tex> p):
j++
p1 = p1.right
'''Связывание''' <tex>\mathrm{fastening (p1, p2, p3)}</tex> трех толстых деревьев ранга <tex>i</tex> в одно толстое дерево ранга <tex>i+1</tex>. Эта функция принимает три указателя <tex>p1, p2 ,p3</tex> на три разных толстых дерева одного и того же ранга <tex>i</tex> и возвращает указатель на вновь сформированное дерево ранга <tex>i+1</tex> .
Процедура заключается в выполнении следующего псевдокода:
'''Node''' fastening ('''Node''' p1, '''Node''' p2, '''Node''' p3): '''if''' (p1.key <tex> \le leqslant </tex> p2.key) '''and''' (p1.Key <tex> \le leqslant </tex> p3.key)
minP = p1
p1 = p2
p2 = p3
'''if''' (p2.key <tex> \le leqslant </tex> p1.key) '''and''' (p2.key <tex> \le leqslant </tex> p3.key)
minP = p2
p1 = p1
p2 = p3
'''if''' (p3.key <tex> \le leqslant </tex> p1.key) '''and''' (p3.key <tex> \le leqslant </tex> p2.key)
minP = p3
p1 = p1
Функция <tex>\mathrm{getKey(p)}</tex> по указателю p на элемент определяет значение его ключа:
<font color=green>//под <tex>\infty</tex> нужно понимать нейтральный относительно минимума элемент.</font>
'''int''' getKey('''Node''' p):
'''if''' p == NULL
min = <tex>\infty</tex>
Функция <tex>\mathrm{minKeyNodeRoot(p)}</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:
'''Node''' minKeyNodeRoot('''Node''' p):
p1 = p
minP = p1
Операция фиксации <tex>\mathrm{rmFixRootCount(i)}</tex> для <tex>i</tex>-го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга <tex>i</tex>, состоящий ровно из трех деревьев. При выполнении этой операции значение в <tex>i</tex>-м разряде — должно стать равным нулю, а значение в <tex>i</tex>-м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга <tex>i</tex>, а количество деревьев ранга <tex>i+1</tex> должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга <tex>i</tex> , связать их в дерево ранга <tex>i+1</tex> и вставить вновь полученное дерево в кучу.
Следует учесть, что ранг нового дерева может стать больше, чем <tex>\mathtt{maxRank}</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>\mathtt{maxRank}</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
'''void''' rmFixRootCount('''int''' i)
'''if''' maxRank == i
maxRank = i + 1
===Инкрементирование i-го разряда корневого счетчика===
По сравнению с описанным алгоритмом инкрементирования <tex>i</tex>-го разряда избыточного представления здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
'''void''' rmIncRootCount('''int''' i,'''Node''' p)
'''if''' (rootCount[i].Value == 1) '''or''' (rootCount[i].Value == 2)
'''if''' rootCount[rootCount[i].forwardPointer].Value == 3
===Удаление дерева из кучи===
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>i</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
'''void''' delete('''int''' i, '''Node''' p):
deleteTree(i, p)
rootCount[i].Value = rootCount[i].Value - 1
===Нахождение дерева с минимальным ключом в корне <tex>\mathrm{minKey()}</tex>===
'''Node''' minKey()
minP = NULL
'''for''' i = 0 to maxRank:
===deleteViolation===
Для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:
'''void''' deleteViolation('''Node''' h2):
'''for''' i = 0 '''to''' h2.maxRank
'''if''' countViolation[i].Value == 2
fixCountViolation(i)
==См. также==* [[Тонкая куча]] ==Источникиинформации==
* [http://www.intuit.ru/studies/courses/100/100/lecture/2935?page=1 INTUIT.ru {{---}} Толстые кучи]
* [https://www.lektorium.tv/lecture/14234 CS center {{---}} Приоритетные очереди]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]

Навигация