64
правки
Изменения
Нет описания правки
*<tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).
Корни деревьев, их которых состоит пирамида, содержатся в так называемом '''списке корней''', при проходе по которому степени соответствующих корней находятся в неубывающем возрастающем порядке.
Доступ к куче осуществляется ссылкой на первый корень в списке корней.
Работа этой процедуры начинается с соединения корневых списков куч в единый список, в котором корневые вершины идут в порядке возрастания неубывания их степеней.
В получившемся списке могут встречаться пары соседних вершин одинаковой степени. Поэтому мы начинаем соединять деревья равной степени и делаем это до тех пор, пока деревьев одинаковой степени не останется. Этот процесс соответствует сложению двоичных чисел столбиком, и время его работы пропорционально числу корневых вершин, то есть операция выполняется за <tex>O(\log(n))</tex>.
</code>
Поскольку минимальный элемент находится в корневом списке, найти его легко; после его удаления соответствующее дерево рассыпается в набор биномиальных деревьев меньшего размера, который надо нужно объединить с оставшейся частью кучи.
Все действия выполняются за время <tex>O(\log n)</tex>, так что общее время работы процедуры есть <tex>O(\log n)</tex>.
=== delete ===
Удаление ключа сводится к операциям decreaseKey и extractMin и decreaseKey: сначала нужно уменьшить ключ до минимально возможного значения, а затем извлечь вершину с минимальным ключом. В процессе выполнения процедуры этот узел всплывает вверх, откуда и удаляется. Процедура выполняется за время <tex>O(\log n)</tex>, поскольку каждая из операций, которые используется в реализаций, работают за <tex>O(\log n)</tex>.
<code>
