1632
правки
Изменения
м
}}
{{Определение
|id=def2
|neat =
|definition=
'''Лес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.
}}
{{Определение
|id=def3
|neat =
|definition=
'''Узел''' (англ. ''Node'') в ''нагруженном лесе'' назовем '''неправильным''', если его ключ меньше ключа его родителя.
}}
{{Определение
|id=def4
|neat =
|definition=
'''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</tex>.
rollbackEdits.php mass rollback
Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log{n})</tex> деревьев.
|proof=
}}
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
Процедура заключается в выполнении следующего псевдокода:
'''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
===Инкрементирование 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 {{---}} Приоритетные очереди]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
