120
правок
Изменения
Псевдокоды операций
}}
Пусть <tex>Node</tex> {{---}} узел тонкого дерева, а <tex>ThinHeap</tex> {{---}} тонкая куча, причем <tex>ThinHeap</tex> содержит ссылки на первый и последний корень <tex>first</tex> и <tex>last</tex> соответственно.
=== makeHeap ===
Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
<code>
</code>
=== insert ===
Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла с ключом <tex>x</tex>, добавить его в корневой список на первое место, если этот ключ минимален, иначе либо на второепоследнее. Потенциал <tex>\Phi</tex> увеличивается на 1. <code> void insert(H, x) if H.first == null H.first = x H.last = x else if x.key < H.first.key x.right = H.first H.first = x else H.last.right = x H.last = x </code>
Стоимость <tex>O(1)</tex>.
Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу списка и вернуть его ключ, потенциал <tex>\Phi</tex> не меняется.
<code>
Node getMin(H)
return H.first
</code>
Стоимость <tex>O(1)</tex>.
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
<code>
ThinHeap meld(H1, H2)
if H1.first == null
return H2
else
if H2.first == null
return H1
else
if H1.first.key < H2.first.key
H1.last.right = H2.first
H1.last = H2.last
return H1
else
H2.last.right = H1.first
H2.last = H1.last
return H2
</code>
Стоимость <tex>O(1)</tex>.
Мы удалили корень из списка за <tex>O(1)</tex>, затем за <tex>O(D(n))</tex> нормализовали детей корня и добавили в корневой список, далее за <tex>O(D(n))+ls</tex> получили новый корневой список, в котором за <tex>O(D(n))</tex> нашли минимальный корень и подвесили список за него.
Получили фактическую стоимость <tex>O(D(n))+ls</tex>. С другой стороны, при добавлении детей в список мы увеличили потенциал <tex>\Phi</tex> не более чем на <tex>O(D(n))</tex>, а каждый связывающий шаг уменьшает наш потенциал <tex>\Phi</tex> на <tex>1</tex>. Отсюда стоимость <tex>O(D(n))=O(\log(n))</tex>.
=== decreaseKey ===
=== delete ===
Чтобы удалить элемент из тонкой кучи нужно сначала выполнить <tex>decreaseKey</tex> этого элемента до <tex>-\infty</tex>, а затем выполнить <tex>extractMin</tex>.
<code>
void delete(H, x)
decreaseKey(H, x, <tex>-\infty</tex>)
extractMin()
</code>
Стоимость <tex>O(\log(n))</tex>.
