1632
правки
Изменения
м
rollbackEdits.php mass rollback
||<tex>\mathrm{getMin}</tex>||<tex>O(1)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm{meldmerge}</tex>||<tex>O(1)</tex>
|-align="center" bgcolor=#FFFFFF
|<tex>\mathrm{extractMin}</tex>||<tex>O(\log(n))</tex>
}}
Пусть <tex>\mathtt{Node}</tex> {{---}} узел тонкого дерева, а <tex>\mathtt{ThinHeap}</tex> {{---}} тонкая куча, причем причём <tex>\mathtt{ThinHeap}</tex> содержит ссылки на первый и последний корень <tex>\mathtt{first}</tex> и <tex>\mathtt{last}</tex> соответственно.
Также введем вспомогательную функцию проверки узла на тонкость, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>\mathtt{Degree(x) - 1}</tex>.
Стоимость <tex>O(1)</tex>.
=== meld merge ===
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
<code>
'''ThinHeap''' meldmerge(H1: '''ThinHeap''', H2: '''ThinHeap'''):
'''if''' H1.first == ''null''
'''return''' H2
