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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлены ссылки)
(decreaseKey)
Строка 6: Строка 6:
  
 
{{Определение
 
{{Определение
|id=thin_tree_def.
+
|id=thin_tree_def
 
|definition='''Тонкое дерево''' (''thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.
 
|definition='''Тонкое дерево''' (''thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.
 
}}
 
}}
Строка 13: Строка 13:
  
 
{{Утверждение
 
{{Утверждение
|id=about_thin_tree_rank.
+
|id=about_thin_tree_rank
 
|statement=Ранг тонкого дерева равен количеству детей его корня.
 
|statement=Ранг тонкого дерева равен количеству детей его корня.
 
}}
 
}}
Строка 23: Строка 23:
 
== Свойства тонкого дерева ==
 
== Свойства тонкого дерева ==
 
{{Утверждение
 
{{Утверждение
|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> помечен (неполный).
Строка 34: Строка 34:
  
 
{{Определение
 
{{Определение
|id=thin_forest_def.
+
|id=thin_forest_def
 
|definition='''Тонкий лес''' (''thin forest'') {{---}} это набор ''тонких деревьев'', ранги которых не обязательно попарно различны.
 
|definition='''Тонкий лес''' (''thin forest'') {{---}} это набор ''тонких деревьев'', ранги которых не обязательно попарно различны.
 
}}
 
}}
  
 
{{Утверждение
 
{{Утверждение
|id=about_thin_forest_with_n_nodes.
+
|id=about_thin_forest_with_n_nodes
 
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
 
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
 
|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальный]] лес является тонким, а для [[Биномиальная куча#Биномиальное дерево|биномиального]] леса рассматриваемое утверждение справедливо.
 
|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальный]] лес является тонким, а для [[Биномиальная куча#Биномиальное дерево|биномиального]] леса рассматриваемое утверждение справедливо.
Строка 45: Строка 45:
  
 
{{Определение
 
{{Определение
|id=thin_heap_def.
+
|id=thin_heap_def
 
|definition='''Тонкая куча''' (''thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный ''тонкий лес''.
 
|definition='''Тонкая куча''' (''thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный ''тонкий лес''.
 
}}
 
}}
Строка 52: Строка 52:
  
 
{{Теорема
 
{{Теорема
|id=max_rank_th.
+
|id=max_rank_th
 
|about=О максимальном ранге узла
 
|about=О максимальном ранге узла
 
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\Phi=\frac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.
 
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\Phi=\frac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.
Строка 61: Строка 61:
 
<tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_i</tex> для <tex>k \geqslant 2</tex>
 
<tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_i</tex> для <tex>k \geqslant 2</tex>
  
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_k \geqslant F_k</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \Phi^{k-1}</tex> хорошо известно.
+
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_k \geqslant F_k</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \Phi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].
  
Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> ''тонкого дерева'' в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi}(n)+1</tex>. Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phi^{D(n)-1}</tex>.
+
Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> ''тонкого дерева'' в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi}(n)+1</tex>.  
 +
 
 +
Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phi^{D(n)-1}</tex>.
  
 
Отсюда следует, что <tex>D(n)\leqslant\log_{\Phi}(n)+1</tex>.
 
Отсюда следует, что <tex>D(n)\leqslant\log_{\Phi}(n)+1</tex>.
Строка 120: Строка 122:
  
 
{{Утверждение
 
{{Утверждение
|id=about_thin_heap_potential.
+
|id=about_thin_heap_potential
 
|statement=Определённый таким образом потенциал обладает свойствами:
 
|statement=Определённый таким образом потенциал обладает свойствами:
 
# <tex>\Phi \geqslant 0</tex>.
 
# <tex>\Phi \geqslant 0</tex>.
Строка 171: Строка 173:
  
 
=== decreaseKey ===
 
=== decreaseKey ===
Чтобы уменьшить ключ элемента нужно:
+
После уменьшения ключа может быть нарушена [[Двоичная куча|кучеобразность]], в этом случае мы переносим все поддерево с корнем в уменьшаемом элементе в корневой список, также обновляем минимум в тонкой куче.
 +
 
 +
Теперь могут быть нарушены свойства тонкого дерева, будем различать два вида нарушений:
 +
* Братские нарушения {{---}} это нарушения [[Тонкая куча#about_thin_tree|третьего свойства]] тонкого дерева.
 +
* Родительские нарушения {{---}} это нарушения [[Тонкая куча#about_thin_tree|первого или второго свойства]] тонкого дерева.
 +
 
 +
Назовем узел <tex>y</tex> узлом локализации братского нарушения среди детей узла <tex>z</tex>, если ранг узла <tex>y</tex> отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1.
 +
 
 +
Назовем узел <tex>y</tex> узлом локализации родительского нарушения, если выполнено одно из трех условий:
 +
# Ранг узла <tex>y</tex> на три больше, чем ранг его самого левого сына.
 +
# Ранг узла <tex>y</tex> равен двум, и он не имеет детей.
 +
# Узел <tex>y</tex> есть помеченный корень дерева.
 +
 
 +
Пусть узел <tex>y</tex> — это узел локализации братского нарушения.
 +
# Узел <tex>y</tex> не помечен, тогда помещаем поддерево с корнем в самом левом сыне узла <tex>y</tex> на место пропущенного в братском списке. Узел <tex>y</tex> становится помеченным, дерево становится корректным, процедура исправления завершается.
 +
# Узел <tex>y</tex> помечен, тогда уменьшаем ранг узла <tex>y</tex> на единицу. Теперь узлом локализации нарушения будет либо левый брат узла <tex>y</tex>, либо его родитель, тогда нарушение станет родительским.
 +
 
 +
С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
 +
 
 +
Пусть узел <tex>y</tex> — это узел локализации родительского нарушения, а узел <tex>z</tex> — родитель узла <tex>y</tex>.
 +
 
 +
Переместим все поддерево с корнем в <tex>y</tex> в корневой список и уменьшим ранг <tex>y</tex>. Если узел <tex>z</tex> не был помечен, то дерево станет корректным, иначе <tex>z</tex> {{---}} новый узел локализации родительского нарушения.
 +
 
 +
Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
 +
 
 +
Каждый промежуточный шаг рекурсии уменьшает количество помеченных узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>.
  
 
Стоимость <tex>O(1)</tex>.
 
Стоимость <tex>O(1)</tex>.
Строка 184: Строка 211:
 
* [http://www.intuit.ru/studies/courses/100/100/lecture/1542 Тонкие кучи  — INTUIT.ru]
 
* [http://www.intuit.ru/studies/courses/100/100/lecture/1542 Тонкие кучи  — INTUIT.ru]
 
* [http://dl.acm.org/citation.cfm?id=1328914 ''Каплан Х.'', ''Тарьян А. Р..'', Thin Heaps, Thick Heaps // ACM Transactions on Algorithms. {{---}} 2008. {{---}} Т.4. {{---}} №1. {{---}} C. 1{{---}}14. {{---}} ISSN: 1549-6325]
 
* [http://dl.acm.org/citation.cfm?id=1328914 ''Каплан Х.'', ''Тарьян А. Р..'', Thin Heaps, Thick Heaps // ACM Transactions on Algorithms. {{---}} 2008. {{---}} Т.4. {{---}} №1. {{---}} C. 1{{---}}14. {{---}} ISSN: 1549-6325]
 +
* [http://www.lektorium.tv/lecture/?id=14233 ''Станкевич А. С.'', Дополнительные главы алгоритмов, лекция 1 {{---}} Лекториум]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]

Версия 09:08, 26 мая 2013

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

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

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

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

Определение:
Тонкое дерево (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]y[/math] узлом локализации братского нарушения среди детей узла [math]z[/math], если ранг узла [math]y[/math] отличается от ранга его ближайшего правого брата на 2, либо он не имеет правого брата и его ранг равен 1.

Назовем узел [math]y[/math] узлом локализации родительского нарушения, если выполнено одно из трех условий:

  1. Ранг узла [math]y[/math] на три больше, чем ранг его самого левого сына.
  2. Ранг узла [math]y[/math] равен двум, и он не имеет детей.
  3. Узел [math]y[/math] есть помеченный корень дерева.

Пусть узел [math]y[/math] — это узел локализации братского нарушения.

  1. Узел [math]y[/math] не помечен, тогда помещаем поддерево с корнем в самом левом сыне узла [math]y[/math] на место пропущенного в братском списке. Узел [math]y[/math] становится помеченным, дерево становится корректным, процедура исправления завершается.
  2. Узел [math]y[/math] помечен, тогда уменьшаем ранг узла [math]y[/math] на единицу. Теперь узлом локализации нарушения будет либо левый брат узла [math]y[/math], либо его родитель, тогда нарушение станет родительским.

С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.

Пусть узел [math]y[/math] — это узел локализации родительского нарушения, а узел [math]z[/math] — родитель узла [math]y[/math].

Переместим все поддерево с корнем в [math]y[/math] в корневой список и уменьшим ранг [math]y[/math]. Если узел [math]z[/math] не был помечен, то дерево станет корректным, иначе [math]z[/math] — новый узел локализации родительского нарушения.

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

Каждый промежуточный шаг рекурсии уменьшает количество помеченных узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость [math]O(1)[/math].

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

delete

Чтобы удалить элемент из тонкой кучи нужно сначала выполнить [math]decreaseKey[/math] этого элемента до [math]-\infty[/math], а затем выполнить [math]extractMin[/math].

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


Источники