635
правок
Изменения
Нет описания правки
==Толстое дерево==
{{Определение
}}
==Толстые кучи==
Здесь и далее "Толстая куча на избыточном счетчике" будет заменено на более лаконичное "Толстая куча".
}}
===Представление толстой кучи===
Каждый узел толстой кучи будем представлять записью со следующими полями:
*<tex>key</tex> {{---}} ключ элемента, приписанного узлу дерева
[[Файл:FatHeapExample.png |400px|thumb|right|Представление леса списком]]
===Вспомогательные структуры===
Нам понадобятся понятия '''корневого счетчика''' и '''счетчика нарушений'''.
Для '''инициализации''' нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга <tex>maxRank + 1</tex>. Это первый момент появления в куче узла ранга <tex>maxRank + 1</tex>. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного <tex>maxRank + 1</tex>, соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
==Основные операции==
* <tex>\mathrm{makeHeap}</tex> {{---}} <tex>O(1)</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 {{---}} Приоритетные очереди]
