Изменения

'''Двоичная куча ''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия: * Значение в любой вершине не больше (если куча для минимума), чем значения её потомков.* На <tex>Ri</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.* Последний слой заполнен слева направо (как показано на рисунке)}}[[Файл:Min_heap.png‎|thumb|325px|Пример кучи для минимума]][[Файл:Min_heap_array.png‎|thumb|325px|Хранение кучи в массиве, красная стрелка {{---}} левый сын, зеленая {{---}} правый]]Удобнее всего двоичную кучу хранить в виде массива <tex>a[0..n-1]</tex>, у которого нулевой элемент, <tex>a[0]</tex> — элемент в корне, а потомками элемента <tex>a[i]</tex> являются <tex>a[2i+1]</tex> и <tex>a[2i+2]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(\log{n})</tex>, где <tex>n</tex> — количество узлов дерева. Чаще всего используют кучи для минимума (когда предок не больше детей) и для максимума (когда предок не меньше детей). Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за <tex>O(\log{n})</tex>. Они являются частным случаем приоритетных очередей. ==Базовые процедуры== ===Восстановление свойств кучи=== Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)и <tex> \mathrm {siftUp} </tex> (просеивание вверх).  ====siftDown====Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>. Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.Процедура выполняется за время <tex>O(\log{n})</tex>. <code style="display:inline-block"> '''function''' siftDown(i : '''int'''): '''while''' 2 * i + 1 < a.heapSize <font color = "green">// heapSize {{---}} количество элементов в куче</font> left = 2 * i + 1 <font color = "green">// left {{---}} левый сын</font> right = 2 * i + 2 <font color = "green">// right {{---}} правый сын</font> j = left '''if''' right < a.heapSize '''and''' a[right] < a[left] j = right '''if''' a[i] <= a[j] '''break''' swap(a[i], a[j]) i = j</code> ====siftUp====Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>. Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>для этого отца. Иными словами, слишком маленький элемент всплывает наверх.Процедура выполняется за время <tex>O(\log{n})</tex>. <code style="display:inline-block"> '''function''' siftUp(i : '''int'''): '''while''' a[i] < a[(i - 1) / 2] <font color = "green">// i <tex>==</tex> 0 {{---}} мы в корне</font> swap(a[i], a[(i - 1) / 2]) i = (i - 1) / 2</code> ===Извлечение минимального элемента=== Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{n} )</tex>.Извлечение выполняется в четыре этапа:# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.# Последний элемент копируется в корень, после чего удаляется из кучи.# Вызывается <math> \mathrm {siftDown} </math> для корня.# Сохранённый элемент возвращается.  '''int''' extractMin(): '''int''' min = a[0] a[0] = a[a.heapSize - 1] a.heapSize = a.heapSize - 1 siftDown(0) '''return''' min ===Добавление нового элемента=== Выполняет добавление элемента в кучу за время <tex>O(\subseteq Alog{n})</tex>.Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \times Amathrm {siftUp} </math>. <code style="display:inline-block"> '''function''' insert(key : '''int'''): a.heapSize = a.heapSize + 1 a[a.heapSize - 1] = key siftUp(a.heapSize - 1)</code> ===Построение кучи за O(n) ==={{Определение | definition ='''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>d</tex>потомков. }} Дан массив <tex>a[0.. n - 1].</tex> Требуется построить <tex>d</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива {{---}} сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента <math>\mathrm {siftUp}</math>. Временная оценка такого алгоритма <tex> O(n\log{n})</tex>. Однако можно построить кучу еще быстрее — такое двоичное за <tex> O(n) </tex>.  Представим, что в массиве хранится дерево(<tex>a[0] - </tex> корень, а потомками элемента <tex>a[i]</tex> являются <tex>a[di+1]...a[di+d]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для которого выполнены три условиявершин, имеющих хотя бы одного потомка:от <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(n) </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> |proof= Обозначим за <tex>s</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_{n = 1}^\infty \limits}\frac{1}{d либо ^n}</tex> {{---}} это сумма бесконечной убывающей геометрической прогрессии, и она равна <tex dpi = "160"> \frac{\frac{1}{d}}{1 -\frac{1}{d}} = \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> <tex dpi = "160"> = \frac{d}{(d - 1)^2}. </tex>