120
правок
Изменения
→Операции над тонкой кучей: extractMin
Пусть <tex>Node</tex> {{---}} узел тонкого дерева, а <tex>ThinHeap</tex> {{---}} тонкая куча, причем <tex>ThinHeap</tex> содержит ссылки на первый и последний корень <tex>first</tex> и <tex>last</tex> соответственно.
Также введем вспомогательную функцию проверки узла на помеченность, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>Degree(x) - 1</tex>.
<code>
bool isMarked(x)
if x.rank == 1
return x.child == null
else
return x.child.rank + 1 != x.rank
</code>
=== makeHeap ===
<code>
ThinHeap makeHeap()
</code>
=== insert ===
Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла <tex>x</tex> с ключом <tex>x.key</tex>, добавить его в корневой список на первое место, если этот ключ минимален, либо на последнее. Потенциал <tex>\Phi</tex> увеличивается на 1.
<code>
При добавлении нового дерева мы, если дерево такого ранга уже есть в массиве, связываем его с существующим и пытаемся добавить новое дерево с рангом на <tex>1</tex> больше.
<code>
Node extractMin(H)
// Удаляем минимальный корень из корневого списка
tmp = H.first
H.first = H.first.right
if H.first == null H.last = null
// Снимаем пометки с его детей и добавляем их в корневой список
x = tmp.first.child
while x != null
if isMarked(x)
x.rank = x.rank - 1
x.left = null
insert(H, x)
x = x.right
// Объединяем все корни одного ранга с помощью вспомогательного массива aux
max = -1
x = H.first
while x != null
while aux[x.rank] != null
next = x.right
if aux[x.rank].key < x.key
swap(aux[x.rank], x)
aux[x.rank].right = x.child
x.child.left = aux[x.rank]
aux[x.rank].left = x
x.child = aux[x.rank]
aux[x.rank] = null
x.rank = x.rank + 1
aux[x.rank] = x
if x.rank > max
max = x.rank
x = next
// Собираем все корни обратно в тонкую кучу
H = makeHeap()
i = 0
while i <= max
insert(H, aux[i])
i = i + 1
return tmp
</code>
Пусть мы сделали <tex>ls</tex> связывающих шагов (''linking steps'') во время добавления в массив.
Стоимость <tex>O(\log(n))</tex>.
= Источники =
