Изменения

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

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

938 байт убрано, 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>.
}}
fixCountViolation(i)
==См. также==* [[Тонкая куча]] ==Источникиинформации==
* [http://www.intuit.ru/studies/courses/100/100/lecture/2935?page=1 INTUIT.ru {{---}} Толстые кучи]
* [https://www.lektorium.tv/lecture/14234 CS center {{---}} Приоритетные очереди]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]

Навигация