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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Амортизационный анализ операций)
м
Строка 8: Строка 8:
 
}}
 
}}
  
Заметим, что у листьев детей нет, а если у корня <tex>B_k</tex> удалить самого левого сына, то <tex>B_k</tex> превратится в <tex>B_{k-1}</tex>. Ранг тонкого дерева равен количеству детей корня.
+
Ограничение на принадлежность внутренним узлам вызвано тем, что у листьев детей нет, а если у корня <tex>B_k</tex> удалить самого левого сына, то <tex>B_k</tex> превратится в <tex>B_{k-1}</tex>.  
  
Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим: <tex>Degree(x)</tex> {{---}} количество детей узла <tex>x</tex>; <tex>Rank(x)</tex> {{---}} ранг соответствующего узла в биномиальном дереве <tex>B_k</tex>.
+
{{Утверждение
 +
|id=about_thin_tree_rank.
 +
|statement=Ранг тонкого дерева равен количеству детей его корня.
 +
}}
 +
 
 +
Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим:
 +
* <tex>Degree(x)</tex> {{---}} количество детей узла <tex>x</tex>.
 +
* <tex>Rank(x)</tex> {{---}} ранг соответствующего узла в биномиальном дереве <tex>B_k</tex>.
  
 
== Свойства тонкого дерева ==
 
== Свойства тонкого дерева ==
 
{{Утверждение
 
{{Утверждение
 
|id=about_thin_tree.  
 
|id=about_thin_tree.  
|statement=Тонкое дерево обладает следующими свойтсвами:
+
|statement=Тонкое дерево обладает следующими свойствами:
 
# Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полный); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (неполный).
 
# Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полный); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (неполный).
 
# Корень не помечен (полный).
 
# Корень не помечен (полный).
 
# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.
 
# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.
# Узел <tex>x</tex> помечен тогда и только тогда, если его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 и он не имеет детей.
+
# Узел <tex>x</tex> помечен тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
 
}}
 
}}
  
Строка 61: Строка 68:
 
== Представление тонкой кучи ==
 
== Представление тонкой кучи ==
  
Поскольку при работе с ''тонкой кучей'' ссылка на родителя требуется только у самого левого ее ребенка, можно хранить ее вместо ссылки на левого сына этой вершины.  
+
''Тонкую кучу'' можно представить как односвязный список корней ''тонких деревьев'', причем корень с минимальным ключом должен быть первым в списке.
 +
 
 +
Поскольку при работе с ''тонкой кучей'' ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины.  
  
 
Таким образом, для эффективной работы ''тонкой кучи'' необходимы следующие поля узла:
 
Таким образом, для эффективной работы ''тонкой кучи'' необходимы следующие поля узла:
Строка 67: Строка 76:
 
*<tex>child</tex> {{---}} указатель на самого левого ребенка узла;
 
*<tex>child</tex> {{---}} указатель на самого левого ребенка узла;
 
*<tex>right</tex> {{---}} указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
 
*<tex>right</tex> {{---}} указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
*<tex>left</tex> {{---}} указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это первый корень списка;
+
*<tex>left</tex> {{---}} указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это корень;
 
*<tex>rank</tex> {{---}} ранг узла (количество дочерних узлов данного узла).
 
*<tex>rank</tex> {{---}} ранг узла (количество дочерних узлов данного узла).
 
Отдельно должен храниться односвязный список корней, корень с минимальным ключом должне быть первым в этом списке.
 
  
 
Для ускорения проверки на ''тонкость'' (''thinness'') можно отдельно хранить помеченность вершины.
 
Для ускорения проверки на ''тонкость'' (''thinness'') можно отдельно хранить помеченность вершины.
 +
Также в вершине можно хранить любую дополнительную информацию.
  
Также в вершине можно хранить любую дополнительную информацию.
+
Для работы с ''тонкой кучей'' достаточно иметь ссылку на ее первый корень.  
  
 
== Операции над тонкой кучей ==
 
== Операции над тонкой кучей ==
  
Рассмотрим операции, которые можно производить над тонкой кучей. Время работы указано в таблице:
+
Рассмотрим операции, которые можно производить над ''тонкой кучей''. Время работы указано в таблице:
 
{| border="1"
 
{| border="1"
 
  |-align="center"
 
  |-align="center"
Строка 103: Строка 111:
 
  |}
 
  |}
  
Многие операции над тонкой кучей выполняются так же, как и над фиббоначиевой.
+
Многие операции над ''тонкой кучей'' выполняются так же, как и над ''фиббоначиевой''.
  
 
Для амортизационного анализа применим метод потенциалов.
 
Для амортизационного анализа применим метод потенциалов.
Строка 113: Строка 121:
 
|statement=Определённый таким образом потенциал обладает свойствами:
 
|statement=Определённый таким образом потенциал обладает свойствами:
 
# <tex>\Phi \geqslant 0</tex>.
 
# <tex>\Phi \geqslant 0</tex>.
# Для пустой кучи <tex>\Phi = 0</tex>.
+
# Для пустой ''тонкой кучи'' <tex>\Phi = 0</tex>.
 
}}
 
}}
  
Строка 119: Строка 127:
 
=== makeHeap ===
 
=== makeHeap ===
  
Возвращаем новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
+
Возвращаем ссылку на новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
  
 
Стоимость <tex>O(1)</tex>.
 
Стоимость <tex>O(1)</tex>.
Строка 137: Строка 145:
 
=== meld ===
 
=== meld ===
  
Сливаем корневые списки, ставя первым тот список, где ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
+
Сливаем корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
  
 
Стоимость <tex>O(1)</tex>.
 
Стоимость <tex>O(1)</tex>.
Строка 147: Строка 155:
 
# Cливаем детей с корневым списком.
 
# Cливаем детей с корневым списком.
 
# Объединяем, пока возможно, тонкие деревья одного ранга.
 
# Объединяем, пока возможно, тонкие деревья одного ранга.
Это можно сделать, например, с помощью вспомогательного массива размером <tex>O(D(n))</tex>, в <tex>i</tex>-ой ячейке которго хранится корень тонкого дерева <tex>T_i</tex> ранга <tex>i</tex>.
+
Это можно сделать, например, с помощью вспомогательного массива размером <tex>O(D(n))</tex>, в <tex>i</tex>-ой ячейке которого хранится корень тонкого дерева <tex>T_i</tex> ранга <tex>i</tex>.
  
 
Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка.
 
Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка.
  
При добавлении нового дерева мы, пока возможно, связываем его с деревом такого же ранга, а затем пытаемся добавить новое дерево с рангом на <tex>1</tex> больше.
+
При добавлении нового дерева мы, если дерево такого ранга уже есть в массиве, связываем его с существующим и пытаемся добавить новое дерево с рангом на <tex>1</tex> больше.
  
Пусть мы сделали <tex>ls</tex> ''связывающих шагов'' (''linking steps'') во время добавления в массив.
+
Пусть мы сделали <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(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>.
 
Получили фактическую стоимость <tex>O(D(n))+O(ls)</tex>. С другой стороны, при добавлении детей в список мы увеличили потенциал <tex>\Phi</tex> не более чем на <tex>O(D(n))</tex>, а каждый связывающий шаг уменьшает наш потенциал <tex>\Phi</tex> на <tex>1</tex>.

Версия 10:51, 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].


Источники