Изменения

'''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:

* Значение в любой вершине не меньше, больше (если куча для максимумаминимума), чем значения её потомков.

 [[Файл:HeapMin_heap.pngpng‎|thumb|325px|Пример кучи для максимумаминимума]][[Файл:Min_heap_array.png‎|thumb|325px|Хранение кучи в массиве, красная стрелка {{---}} левый сын, зеленая {{---}} правый]]Удобнее всего двоичную кучу хранить в виде массива <tex>Aa[0..n-1]</tex>, у которого нулевой элемент, <tex>Aa[0]</tex> — элемент в корне, а потомками элемента <tex>Aa[i]</tex> являются <tex>Aa[2i+1]</tex> и <tex>Aa[2i+2]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{Nn})</tex>, где <tex>Nn</tex> — количество узлов дерева.

Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за <tex>O(\log{Nn})</tex>. Двоичные кучи — частный случай Они являются частным случаем приоритетных очередей. '''Приоритетная очередь''' {{---}} это структура данных, которая позволяет хранить пары (значение и ключ) и поддерживает операции добавления пары, поиска пары с минимальным ключом и ее извлечение.

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры sift_down (просеивание вниз)и sift_up (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией sift_down(i).Работа процедуры: если <tex>i\mathrm {siftDown} </tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем sift_down(просеивание вниз) для этого сына.Процедура выполняется за время и <tex>O(\logmathrm {NsiftUp})</tex>(просеивание вверх).

====siftDown====Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>. Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.Процедура выполняется за время <tex>O(\log{n})</tex>. <codestyle="display:inline-block"> sift_down'''function''' siftDown(i: '''int'''): '''while''' 2 * i + 1 < a.heapSize <font color = "green">// heap_size heapSize {{--- }} количество элементов в куче if (2 * i + 1 <= A.heap_size) /font> left = A[2 * i + 1] <font color = "green">// left {{---}} левый сын</font> else left right = inf if (2 * i + 2 <font color = A.heap_size) right = A[2 * i + 2] "green">// right {{---}} правый сын</font> else right j = inf if (left == right == inf) return '''if (''' right <= left && a.heapSize '''and''' a[right ] < Aa[ileft]) swap(A j = right '''if''' a[2 * i + 2], A<= a[ij]) sift_down(2 * i + 2) if (left < A[i]) '''break''' swap(Aa[2 * i + 1], Aa[ij]) sift_down(2 * i + 1) = j

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем sift_up====siftUp====для этого отца. Иными словамиЕсли значение измененного элемента уменьшается, слишком большой элемент всплывает наверх.Процедура выполняется за время то свойства кучи восстанавливаются функцией <tex>O(\logmathrm {NsiftUp})</tex>.

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} <code/tex> sift_upдля этого отца. Иными словами, слишком маленький элемент всплывает наверх.Процедура выполняется за время <tex>O(i\log{n})</tex>. <code style="display:inline-block"> if '''function''' siftUp(i == 0: '''int''') return //Мы в корне: if (A '''while''' a[i] < Aa[(i - 1) / 2]) <font color = "green">// i <tex>==</tex> 0 {{---}} мы в корне</font> swap(Aa[i], Aa[(i - 1) / 2]); sift_up i = (i - 1) / 2)

Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{Nn})</tex>.

# Вызывается sift_down(i) <math> \mathrm {siftDown} </math> для корня.

<code> extract_min'''int''' extractMin(): '''int''' min = Aa[0] A a[0] = Aa[Aa.heap_size heapSize - 1] A a.heap_size heapSize = Aa.heap_size heapSize - 1 sift_down siftDown(0) '''return ''' min</code>

Выполняет добавление элемента в кучу за время <tex>O(\log{Nn})</tex>.Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры sift_up<math> \mathrm {siftUp} </math>.

<codestyle="display:inline-block"> '''function''' insert(key: '''int'''): A a.heap_size heapSize = Aa.heap_size heapSize + 1 A a[Aa.heap_size heapSize - 1] = key sift_up siftUp(Aa.heap_size heapSize - 1)

===Построение кучи за O(Nn) ==={{Определение | definition ='''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>d</tex> потомков. }} Дан массив <tex> Aa[0.. n - 1]. </tex> Требуется построить <tex>d</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива – это {{---}} сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы (сделать sift_down)в конец кучи и запускать от каждого добавленного элемента <math>\mathrm {siftUp}</math>. Временная оценка такого алгоритма <tex> O(Nn\log{Nn})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(Nn) </tex>.  Представим, что в массиве хранится дерево ( <tex>Aa[0]- </tex> — корень, а потомками элемента <tex>Aa[i]</tex> являются <tex>Aa[2idi+1]...a[di+d]</tex> и ). Сделаем <tex>A[2i+2]\mathrm {siftDown} </tex>). Делаем sift_down для вершин , имеющих хотя бы одного потомка (: от <tex dpi=140>\dfrac{n}{d}</tex> до <tex>0</tex>,{{---}} так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены). На выходе получим искомую кучу.

|statement= На выходе получим искомую кучу. |proof= До вызова <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами. После выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.}}{{Лемма|statement= Время работы этого алгоритма <tex> O(Nn) </tex>.|proof= Число вершин на высоте <tex>h</tex> в куче из <tex>n</tex> элементов не превосходит <tex dpi = "160"> \left \lceil \frac{n}{d^h} \right \rceil </tex>. Высота кучи не превосходит <tex> \log_{d}n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит <tex dpi = "160"> \sum_{h = 1}^H \limits\frac{n}{d^h} \cdot d </tex> <tex dpi = "150"> \cdot h </tex> <tex dpi = "160"> = n \cdot d \cdot {\sum_{h = 1}^H \limits}\frac{h}{d^h}. </tex> Докажем вспомогательную лемму о сумме ряда. {{Лемма|statement= <tex dpi = "160"> {\sum_{h = 1}^\infty \limits}\frac{h}{d^h} = \frac{d}{(d - 1)^2} . </tex>

Число вершин на высоте Обозначим за <tex>hs</tex> в куче из <tex>n</tex> элементов не превосходит сумму ряда. Заметим, что<tex dpi = "160"> \left \lceil \frac{n}{2d^hn} = \right \rceil </tex>. Высота кучи не превосходит <tex> \log_frac{21} n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит <tex dpi = "160"> \sum_{h = 1d}^H \limitscdot \frac{n- 1}{2d ^h}</tex> <tex dpi = "150"> \cdot h </tex> <tex dpi = "160">= {n \cdot {\sum_{h = - 1}^H \limits}+ \frac{h1}{2d^hn}. </tex>

<tex dpi = "160"> {\sum_{h n = 1}^\infty \limits}\frac{h1}{2d^hn}</tex> {{---}} это сумма бесконечной убывающей геометрической прогрессии, и она равна <tex dpi = "160"> \frac{\frac{1}{d}}{1 - \frac{1}{d}} = 2 \frac{1}{d - 1}. </tex> .

Далее, будет подсчитана эта сумма в общем видеПолучаем <tex>s</tex> <tex dpi = "160" >=\frac{1}{d}</tex> <tex>\cdot s +</tex> <tex dpi = "160" > \frac{1}{d - 1}. Получаем оценку </tex> Откуда <tex>s</tex> <texdpi = "160"> O = \frac{d}{(Nd - 1) ^2}. </tex>.

Все операцииПодставляя в нашу формулу результат леммы, которые делались c бинарной кучей, допустимы и для получаем <tex >n</tex> <texdpi = "160">\cdot (\frac {d}{d - 1})^2 </tex> - кучи. Посчитаем время построения <tex> d \leqslant 4 \cdot n </tex> - кучи<tex>=O(n). В этом случае время работы не превзойдет </tex dpi >}} Псевдокод алгоритма:<code style= "140display:inline-block">N \cdot d '''function''' buldHeap(): '''for''' i = a.heapSize / 2 '''downto''' 0 siftDown(i)</code> ===Слияние двух куч===Даны две кучи <tex>a</tex> и <tex>b</tex>, размерами <tex>n</tex> и <tex>m</tex dpi >, требуется объединить эти две кучи. ====Наивная реализация==== "160" Поочередно добавим все элементы из <tex>b</tex> в <tex>a</tex> \cdot . Время работы {\sum_{i = 1---}^H \limits}<tex>O(m \frac{i}{d^i} log(n+m))</tex>.<code style="display:inline-block"> '''function''' merge(a, b : '''Heap'''): '''while''' b.heapSize > 0 a.insert(b.extractMin())</code> ====Реализация с помощью построения кучи====Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи.Процедура выполняется за время <tex>O(n + m)</tex> .

Здесь появился множитель <texcode style="display:inline-block"> d </tex> из '''function''' merge(a, b : '''Heap'''): '''for''' i = 0 '''to''' b.heapSize - 1 a.heapSize = a.heapSize + 1 a[a.heapSize -за того, что поиск минимума в sift_down происходит за <tex> d 1] = b[i] a.heapify()</texcode>.

Посчитаем ряд <tex dpi = "160"> {\sum_{n = 1}^\infty \limits}\frac{n}{d^n} </tex>. Обозначим за =Поиск k-ого элемента (очень коряво расписано с неверными индексами)===Требуется найти <tex> Sk</tex> сумму ряда. Заметим, что<tex dpi = "160"> \frac{n}{d^n} = \frac{1}{d} \cdot \frac{n - 1}{d ^{n - 1}} + \frac{1}{d^n}ый по величине элемент в куче. </tex>

# Создаем новую кучу, в которой будем хранить пару <tex dpi = "160">{\sum_langle \mathtt{n = 1value}^, \infty \limitsmathtt{index}\frac{1}{d^n} rangle</tex> это сумма бесконечной убывающей геометрической прогрессии ее сумма равна , где <tex dpi = "160"> \frac{\fracmathtt{1value}</tex> {d}}{1 - \frac{1--}{d}} = значение элемента, а <tex>\fracmathtt{1index}</tex> {{d - 1--}}индекс элемента в основном массиве, и добавляем в нее корень кучи. # Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <tex>k - 1</tex> раз.# В корне новой кучи будет находиться ответ.

Получаем <tex> S </tex> <tex dpi = "160" >= \fracВремя работы алгоритма {1}{d}</tex> <tex>\cdot S</tex> <tex dpi = "160" > + \frac{1---}{d - 1}. </tex> Откуда <tex> S</tex> <tex dpi = "160"> = O(k \frac{d}{(d - 1log k)^2}. </tex>.

Подставляя в формулу для суммы получаем <tex > N При </tex> <tex dpi = "160">n \cdot (lessapprox k \frac {d}{d - 1})^2 </tex> <tex> < 5 \cdot N log k </tex>выгоднее запускать [[поиск k-ой порядковой статистики]].([[Файл:Min_heap_kth.png‎|thumb|center|650px|Пример при <tex>d k = 25</tex> получаем двоичную кучу) , красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]

Получаем время работы <tex> O(N) </tex>== См.также ==* [[Биномиальная куча]]* [[Фибоначчиева куча]]* [[Левосторонняя куча]]

== Источники информации ==* [http[wikipedia://ru.wikipedia.org/wiki/Min:Двоичная куча|Википедия {{---heap }} Двоичная куча — Wikipedia]]* [http[wikipedia://ru.wikipedia.org/wiki/%D0%9E%D1%87%D0%B5%D1%80%D0%B5%D0%B4%D1%8C_%D1%81_%D0%BF%D1%80%D0%B8%D0%BE%D1%80%D0%B8%D1%82%D0%B5%D1%82%D0%BE%D0%BC :Очередь с приоритетом|Википедия {{---}} Очередь с приоритетом — ]]* [[wikipedia:en:Binary heap|Wikipedia {{---}} Binary heap]]* [[wikipedia:en:Priority queue|Wikipedia{{---}} Priority queue]]