Тонкая куча — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Амортизационный анализ операций)
Строка 14: Строка 14:
 
== Свойства тонкого дерева ==
 
== Свойства тонкого дерева ==
 
{{Утверждение
 
{{Утверждение
|id=about_node_degrees.  
+
|id=about_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> помечен (неполный).
+
|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.
+
# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.
|statement=Корень не помечен (полный).
+
# Узел <tex>x</tex> помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.
}}
 
{{Утверждение
 
|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 и он не имеет детей.
 
 
}}
 
}}
  
Строка 86: Строка 78:
 
== Операции над тонкой кучей ==
 
== Операции над тонкой кучей ==
  
Рассмотрим операции, которые можно производить с тонкой кучей. Время работы указано в таблице:
+
Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
 
{| border="1"
 
{| border="1"
 
  |-align="center"
 
  |-align="center"
Строка 113: Строка 105:
 
Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.
 
Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.
  
 +
Для амортизационного анализа применим метод потенциалов.
 +
 +
Пусть функция потенциала определена как <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 ===
 
=== makeHeap ===
  
Возвращаем новый пустой корневой список. Время <tex>O(1)</tex>.
+
Возвращаем новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
 +
 
 +
Стоимость <tex>O(1)</tex>.
  
 
=== insert ===
 
=== insert ===
  
Создаем новое тонкое дерево из единственного узла с ключом <tex>x</tex>, добавляем в корневой список на первое место, если ключ минимален, иначе на второе. Время <tex>O(1)</tex>.
+
Создаем новое тонкое дерево из единственного узла с ключом <tex>x</tex>, добавляем в корневой список на первое место, если ключ минимален, иначе на второе. Потенциал <tex>\Phi</tex> увеличивается на 1.
 +
 
 +
Стоимость <tex>O(1)</tex>.
  
 
=== getMin ===
 
=== getMin ===
  
Обращаемся к первому корневому узлу списка. Время <tex>O(1)</tex>.
+
Обращаемся к первому корневому узлу списка, потенциал <tex>\Phi</tex> не меняется.  
 +
 
 +
Стоимость <tex>O(1)</tex>.
  
 
=== meld ===
 
=== meld ===
  
Сливаем корневые списки, ставя первым тот список, где ключ первого корня минимален. Время <tex>O(1)</tex>.
+
Сливаем корневые списки, ставя первым тот список, где ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
 +
 
 +
Стоимость <tex>O(1)</tex>.
  
 
=== extractMin ===
 
=== extractMin ===
  
Удаляем корень с минимальным ключом из корневого списка, затем для всех его тонких детей уменьшаем ранг и делаем их нормальными, после чего сливаем детей с корневым списком и объединяем, пока возможно, тонкие деревья одного ранга.
+
# Удаляем корень с минимальным ключом из корневого списка.
Время <tex>O(\log(n))</tex>.
+
# Для всех его помеченных детей уменьшаем ранг и делаем их нормальными.
 +
# 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 ===
 
=== decreaseKey ===
  
Время <tex>O(1)</tex>.
+
Стоимость <tex>O(1)</tex>.
  
 
=== delete ===
 
=== delete ===
Сначала выполняем <tex>decreaseKey</tex> этого элемента до <tex>-\infty</tex>, затем выполняем <tex>extractMin</tex>. Время <tex>O(\log(n))</tex>.
+
Сначала выполняем <tex>decreaseKey</tex> этого элемента до <tex>-\infty</tex>, затем выполняем <tex>extractMin</tex>.  
 +
 
 +
Стоимость <tex>O(\log(n))</tex>.
  
  

Версия 10:21, 24 мая 2013

Тонкая куча — это структура данных, реализующая приоритетную очередь с теми же асимптотическими оценками, что и фиббоначиева куча, но имеющая большую практическую ценность из-за меньших констант.

Тонкие кучи, как и многие другие кучеобразные структуры, аналогичны биномиальным кучам.

Тонкое дерево

Определение:
Тонкое дерево (thin tree) [math]T_k[/math] ранга [math]k[/math] — это дерево, которое может быть получено из биномиального дерева [math]B_k[/math] удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.


Заметим, что у листьев детей нет, а если у корня [math]B_k[/math] удалить самого левого сына, то [math]B_k[/math] превратится в [math]B_{k-1}[/math]. Ранг тонкого дерева равен количеству детей корня.

Для любого узла [math]x[/math] в дереве [math]T_k[/math] обозначим: [math]Degree(x)[/math] — количество детей узла [math]x[/math]; [math]Rank(x)[/math] — ранг соответствующего узла в биномиальном дереве [math]B_k[/math].

Свойства тонкого дерева

Утверждение:
Тонкое дерево обладает следующими свойтсвами:
  1. Для любого узла [math]x[/math] либо [math]Degree(x)=Rank(x)[/math], в этом случае говорим, что узел [math]x[/math] не помечен (полный); либо [math]Degree(x)=Rank(x)-1[/math], в этом случае говорим, что узел [math]x[/math] помечен (неполный).
  2. Корень не помечен (полный).
  3. Для любого узла [math]x[/math] ранги его детей от самого правого к самому левому равны соответственно [math]0,1,2,...,Degree(x)-1[/math].
  4. Узел [math]x[/math] помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.

Тонкая куча

Определение:
Тонкий лес (thin forest) — это набор тонких деревьев, ранги которых не обязательно попарно различны.


Утверждение:
Для любого натурального числа [math]n[/math] существует тонкий лес, который содержит ровно [math]n[/math] элементов и состоит из тонких деревьев попарно различных рангов.
[math]\triangleright[/math]
Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.
[math]\triangleleft[/math]


Определение:
Тонкая куча (thin heap) — это кучеобразно нагруженный тонкий лес.


Пусть [math]D(n)[/math] — максимально возможный ранг узла в тонкой куче, содержащей [math]n[/math] элементов.

Теорема (О максимальном ранге узла):
В тонкой куче из [math]n[/math] элементов [math]D(n) \leqslant \log_{\Phi} n[/math], где [math]\Phi=\frac{1+\sqrt{5}}{2}[/math] — золотое сечение.
Доказательство:
[math]\triangleright[/math]

Сначала покажем, что узел ранга [math]k[/math] в тонком дереве имеет не менее [math]F_k \geqslant \Phi^{k-1}[/math] потомков, включая самого себя, где [math]F_k[/math][math]k[/math]-е число Фибоначчи, определяемое соотношениями [math]F_0=1[/math], [math]F_1=1[/math], [math]F_k=F_{k-2}+F_{k-1}[/math] для [math]k \geqslant 2[/math].

Действительно, пусть [math]T_k[/math] — минимально возможное число узлов, включая самого себя, в тонком дереве ранга [math]k[/math]. По свойствам [math]1[/math] и [math]3[/math] тонкого дерева получаем следующие соотношения:

[math]T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_i[/math] для [math]k \geqslant 2[/math]

Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что [math]T_k \geqslant F_k[/math] для любых [math]k[/math]. Неравенство [math]F_k \geqslant \Phi^{k-1}[/math] хорошо известно.

Теперь убедимся в том, что максимально возможный ранг [math]D(n)[/math] тонкого дерева в тонкой куче, содержащей [math]n[/math] элементов, не превосходит числа [math]\log_{\Phi}(n)+1[/math]. Действительно, выберем в тонкой куче дерево максимального ранга. Пусть [math]n^*[/math] — количество вершин в этом дереве, тогда [math]n \geqslant n^* \geqslant \Phi^{D(n)-1}[/math].

Отсюда следует, что [math]D(n)\leqslant\log_{\Phi}(n)+1[/math].
[math]\triangleleft[/math]

Представление тонкой кучи

Поскольку при работе с тонкой кучей ссылка на родителя требуется только у самого левого ее ребенка, можно хранить ее вместо ссылки на левого сына этой вершины.

Таким образом, для эффективной работы тонкой кучи необходимы следующие поля узла:

  • [math]key[/math] — ключ (вес) элемента;
  • [math]child[/math] — указатель на самого левого ребенка узла;
  • [math]right[/math] — указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
  • [math]left[/math] — указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это первый корень списка;
  • [math]rank[/math] — ранг узла (количество дочерних узлов данного узла).

Отдельно должен храниться односвязный список корней, корень с минимальным ключом должне быть первым в этом списке.

Для ускорения проверки на тонкость (thinness) можно отдельно хранить помеченность вершины.

Также в вершине можно хранить любую дополнительную информацию.

Операции над тонкой кучей

Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:

[math]makeHeap[/math] [math]O(1)[/math]
[math]insert[/math] [math]O(1)[/math]
[math]getMin[/math] [math]O(1)[/math]
[math]meld[/math] [math]O(1)[/math]
[math]extractMin[/math] [math]O(\log(n))[/math]
[math]decreaseKey[/math] [math]O(1)[/math]
[math]delete[/math] [math]O(\log(n))[/math]

Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.

Для амортизационного анализа применим метод потенциалов.

Пусть функция потенциала определена как [math]\Phi = n + 2 \cdot m[/math] где [math]n[/math] — это количество тонких деревьев в куче, а [math]m[/math] — это количество помеченных вершин.

Утверждение:
Определённый таким образом потенциал обладает свойствами:
  1. [math]\Phi \geqslant 0[/math].
  2. Для пустой кучи [math]\Phi = 0[/math].


makeHeap

Возвращаем новый пустой корневой список, его потенциал [math]\Phi=0[/math].

Стоимость [math]O(1)[/math].

insert

Создаем новое тонкое дерево из единственного узла с ключом [math]x[/math], добавляем в корневой список на первое место, если ключ минимален, иначе на второе. Потенциал [math]\Phi[/math] увеличивается на 1.

Стоимость [math]O(1)[/math].

getMin

Обращаемся к первому корневому узлу списка, потенциал [math]\Phi[/math] не меняется.

Стоимость [math]O(1)[/math].

meld

Сливаем корневые списки, ставя первым тот список, где ключ первого корня минимален. Суммарный потенциал [math]\Phi[/math] не меняется.

Стоимость [math]O(1)[/math].

extractMin

  1. Удаляем корень с минимальным ключом из корневого списка.
  2. Для всех его помеченных детей уменьшаем ранг и делаем их нормальными.
  3. Cливаем детей с корневым списком.
  4. Объединяем, пока возможно, тонкие деревья одного ранга.

Это можно сделать, например, с помощью вспомогательного массива размером [math]O(D(n))[/math], в [math]i[/math]-ой ячейке которго хранится корень тонкого дерева [math]T_i[/math] ранга [math]i[/math].

Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка.

При добавлении нового дерева мы, пока возможно, связываем его с деревом такого же ранга, а затем пытаемся добавить новое дерево с рангом на [math]1[/math] больше.

Пусть мы сделали [math]ls[/math] связывающих шагов (linking steps) во время добавления в массив.

Мы удалили корень из списка за [math]O(1)[/math], затем за [math]O(D(n))[/math] нормализовали детей корня и добавили в корневой список, а затем за [math]O(D(n))+O(ls)[/math] получили новый корневой список, в котором за [math]O(D(n))[/math] нашли минимальный корень и подвесили список за него.

Получили фактическую стоимость [math]O(D(n))+O(ls)[/math]. С другой стороны, при добавлении детей в список мы увеличили потенциал [math]\Phi[/math] не более чем на [math]O(D(n))[/math], а каждый связывающий шаг уменьшает наш потенциал [math]\Phi[/math] на [math]1[/math].

Cтоимость [math]O(D(n))=O(\log(n))[/math].

decreaseKey

Стоимость [math]O(1)[/math].

delete

Сначала выполняем [math]decreaseKey[/math] этого элемента до [math]-\infty[/math], затем выполняем [math]extractMin[/math].

Стоимость [math]O(\log(n))[/math].


Источники