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
===Нахождение дерева с минимальным ключом в корне <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 {{---}} Приоритетные очереди]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
