497
правок
Изменения
→Счетчик нарушений
Для '''инициализации''' нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга <tex>MaxRank + 1</tex>. Это первый момент появления в куче узла ранга <tex>MaxRank + 1</tex>. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного <tex>MaxRank + 1</tex>, соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
{{Утверждение
|id=
|author=
|about= о счетчике нарушений
|statement=
из определения '''счетчика нарушений''' следует:
*Наличие счетчика нарушений позволяет иметь доступ к любому неправильному узлу ранга <tex>i</tex> за время <tex>O(1)</tex> .
*Уменьшение ключа у элемента ранга <tex>i</tex> соответствует операции инкрементирования <tex>i</tex>-го разряда счетчика нарушений ''(естественно, лишь в случае, когда новое значение ключа у изменяемого узла становится меньше значения ключа его родителя)''.
*Операции инкрементирования и декрементирования <tex>i</tex>-го разряда осуществляются за время <tex>O(1)</tex>.
|proof=
}}
=Основные операции=
