120
правок
Изменения
Амортизационный анализ операций
== Свойства тонкого дерева ==
{{Утверждение
|id=about_node_degreesabout_thin_tree. |statement=Тонкое дерево обладает следующими свойтсвами:# Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полный); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (неполный).}}{{Утверждение|id=about_root. |statement=# Корень не помечен (полный).}}{{Утверждение|id=about_children_ranks. |statement=# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.}}{{Утверждение|id=about_marked_nodes. |statement=# Узел <tex>x</tex> помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.
}}
== Операции над тонкой кучей ==
Рассмотрим операции, которые можно производить с над тонкой кучей. Время работы указано в таблице:
{| border="1"
|-align="center"
Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.
Для амортизационного анализа применим метод потенциалов.
Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество ''тонких деревьев'' в куче, а <tex>m</tex> {{---}} это количество помеченных вершин.
{{Утверждение
|id=about_thin_heap_potential.
|statement=Определённый таким образом потенциал обладает свойствами:
# <tex>\Phi \geqslant 0</tex>.
# Для пустой кучи <tex>\Phi = 0</tex>.
}}
=== makeHeap ===
Возвращаем новый пустой корневой список, его потенциал <tex>\Phi=0</tex>. Время Стоимость <tex>O(1)</tex>.
=== insert ===
Создаем новое тонкое дерево из единственного узла с ключом <tex>x</tex>, добавляем в корневой список на первое место, если ключ минимален, иначе на второе. Время Потенциал <tex>\Phi</tex> увеличивается на 1. Стоимость <tex>O(1)</tex>.
=== getMin ===
Обращаемся к первому корневому узлу списка, потенциал <tex>\Phi</tex> не меняется. Время Стоимость <tex>O(1)</tex>.
=== meld ===
Сливаем корневые списки, ставя первым тот список, где ключ первого корня минимален. Время Суммарный потенциал <tex>\Phi</tex> не меняется. Стоимость <tex>O(1)</tex>.
=== extractMin ===
# Удаляем корень с минимальным ключом из корневого списка, затем для .# Для всех его тонких помеченных детей уменьшаем ранг и делаем их нормальными, после чего сливаем .# Cливаем детей с корневым списком и объединяем.# Объединяем, пока возможно, тонкие деревья одного ранга.Время Это можно сделать, например, с помощью вспомогательного массива размером <tex>O(D(n))</tex>, в <tex>i</tex>-ой ячейке которго хранится корень тонкого дерева <tex>T_i</tex> ранга <tex>i</tex>. Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка. При добавлении нового дерева мы, пока возможно, связываем его с деревом такого же ранга, а затем пытаемся добавить новое дерево с рангом на <tex>1</tex> больше. Пусть мы сделали <tex>ls</tex> ''связывающих шагов'' (''linking steps'') во время добавления в массив. Мы удалили корень из списка за <tex>O(1)</tex>, затем за <tex>O(D(n))</tex> нормализовали детей корня и добавили в корневой список, а затем за <tex>O(D(n))+O(ls)</tex> получили новый корневой список, в котором за <tex>O(D(n))</tex> нашли минимальный корень и подвесили список за него. Получили фактическую стоимость <tex>O(D(n))+O(ls)</tex>. С другой стороны, при добавлении детей в список мы увеличили потенциал <tex>\Phi</tex> не более чем на <tex>O(D(n))</tex>, а каждый связывающий шаг уменьшает наш потенциал <tex>\Phi</tex> на <tex>1</tex>. Cтоимость <tex>O(D(n))=O(\log(n))</tex>.
=== decreaseKey ===
=== delete ===
Сначала выполняем <tex>decreaseKey</tex> этого элемента до <tex>-\infty</tex>, затем выполняем <tex>extractMin</tex>. Время Стоимость <tex>O(\log(n))</tex>.
