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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Построение кучи за O(N))
м (rollbackEdits.php mass rollback)
 
(не показано 125 промежуточных версий 22 участников)
Строка 1: Строка 1:
 
==Определение==
 
==Определение==
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Двоичная куча''' или '''пирамида''' — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:
+
'''Двоичная куча''' или '''пирамида''' (англ. ''Binary heap'') — такое двоичное [[Дерево, эквивалентные определения|подвешенное дерево]], для которого выполнены следующие три условия:
  
* Значение в любой вершине не меньше, (если куча для максимума), чем значения её потомков.
+
* Значение в любой вершине не больше (если куча для минимума), чем значения её потомков.
 
* На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
 
* На <tex>i</tex>-ом слое <tex>2^i</tex> вершин, кроме последнего. Слои нумеруются с нуля.
 
* Последний слой заполнен слева направо (как показано на рисунке)
 
* Последний слой заполнен слева направо (как показано на рисунке)
 
}}
 
}}
 
+
[[Файл:Min_heap.png‎|thumb|325px|Пример кучи для минимума]]
[[Файл: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>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>O(\log{n})</tex>. Они являются частным случаем приоритетных очередей.
  
 
==Базовые процедуры==
 
==Базовые процедуры==
Строка 22: Строка 20:
 
===Восстановление свойств кучи===
 
===Восстановление свойств кучи===
  
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры sift_down (просеивание вниз)
+
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
и sift_up (просеивание вверх).  
+
и <tex> \mathrm {siftUp} </tex> (просеивание вверх).  
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией sift_down(i).
+
 
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем sift_down() для этого сына.
+
====siftDown====
Процедура выполняется за время <tex>O(\log{N})</tex>.
+
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.
  
<code>
+
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
  sift_down(i)
+
Процедура выполняется за время <tex>O(\log{n})</tex>.
  // heap_size - количество элементов в куче
+
 
  if (2 * i + 1 <= A.heap_size)
+
<code style="display:inline-block">
    left = A[2 * i + 1] // левый сын
+
  '''function''' siftDown(i : '''int'''):
  else
+
    '''while''' 2 * i + 1 < a.heapSize    <font color = "green">// heapSize {{---}} количество элементов в куче</font>
    left = inf
+
        left = 2 * i + 1             <font color = "green">// left {{---}} левый сын</font>
  if (2 * i + 2 <= A.heap_size)
+
        right = 2 * i + 2           <font color = "green">// right {{---}} правый сын</font>
    right = A[2 * i + 2] // правый сын
+
        j = left
  else
+
        '''if''' right < a.heapSize '''and''' a[right] < a[left]
    right = inf
+
            j = right
  if (left == right == inf) return
+
        '''if''' a[i] <= a[j]
  if (right <= left && right < A[i])
+
            '''break'''
    swap(A[2 * i + 2], A[i])
+
        swap(a[i], a[j])
    sift_down(2 * i + 2) 
+
        i = j
  if (left < A[i])
 
    swap(A[2 * i + 1], A[i])
 
    sift_down(2 * i + 1)
 
 
</code>
 
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией sift_up(i).
 
  
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем sift_up
+
====siftUp====
для этого отца. Иными словами, слишком большой элемент всплывает наверх.
+
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.
Процедура выполняется за время <tex>O(\log{N})</tex>.  
 
  
<code>
+
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>
sift_up(i)
+
для этого отца. Иными словами, слишком маленький элемент всплывает наверх.
  if (i == 0) return //Мы в корне
+
Процедура выполняется за время <tex>O(\log{n})</tex>.
  if (A[i] < A[i / 2])
+
<code style="display:inline-block">
    swap(A[i], A[i / 2]);
+
  '''function''' siftUp(i : '''int'''):
    sift_up(i / 2)
+
    '''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>
 
</code>
  
 
===Извлечение минимального элемента===
 
===Извлечение минимального элемента===
  
Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{N})</tex>.
+
Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{n})</tex>.
 
Извлечение выполняется в четыре этапа:
 
Извлечение выполняется в четыре этапа:
 
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
 
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
 
# Последний элемент копируется в корень, после чего удаляется из кучи.
 
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается sift_down(i) для корня.
+
# Вызывается <math> \mathrm {siftDown} </math> для корня.
 
# Сохранённый элемент возвращается.
 
# Сохранённый элемент возвращается.
<code>
+
 
  extract_min()
+
  '''int''' extractMin():
  min = A[0]
+
    '''int''' min = a[0]
  A[0] = A[A.heap_size - 1]
+
    a[0] = a[a.heapSize - 1]
  A.heap_size = A.heap_size - 1
+
    a.heapSize = a.heapSize - 1
  sift_down(0)
+
    siftDown(0)
  return min
+
    '''return''' min
</code>
 
  
 
===Добавление нового элемента===
 
===Добавление нового элемента===
  
Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
+
Выполняет добавление элемента в кучу за время <tex>O(\log{n})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры sift_up.
+
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \mathrm {siftUp} </math>.
  
<code>
+
<code style="display:inline-block">
  insert(key)
+
  '''function''' insert(key : '''int'''):
  A.heap_size = A.heap_size + 1
+
    a.heapSize = a.heapSize + 1
  A[A.heap_size - 1] = key
+
    a[a.heapSize - 1] = key
  sift_up(A.heap_size - 1)
+
    siftUp(a.heapSize - 1)
 
</code>
 
</code>
  
==Построение кучи за O(N) ==
+
===Построение кучи за O(n) ===
Дан массив <tex> A[0.. n - 1]. </tex> Требуется построить кучу с минимумом в корне. Наиболее очевидный способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы (сделать  sift_down). Временная оценка такого алгоритма <tex> O(N\log{N})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(N) </tex>.  
+
{{Определение | definition =
Представим, что в массиве хранится дерево ( <tex>A[0]</tex> корень, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i+1]</tex> и <tex>A[2i+2]</tex>). Делаем sift_down для вершин имеющих хотя бы одного потомка (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены). На выходе получим искомую кучу.  
+
'''<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= Время работы этого алгоритма <tex> O(N) </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=
 
|proof=
Число вершин на высоте <tex>h</tex> в куче из <tex>n</tex> элементов не превосходит <tex dpi = "160"> \left \lceil \frac{n}{2^h} \right \rceil </tex>.  Высота кучи не превосходит <tex> \log_{2} n </tex>. Обозначим за <tex> H </tex> высоту дерева, тогда время построения не превосходит <tex dpi = "160"> \sum_{h = 1}^H  \limits\frac{n}{2^h}</tex> <tex dpi = "150">  \cdot  h </tex> <tex  dpi = "160">= n \cdot {\sum_{h = 1}^H  \limits}\frac{h}{2^h}. </tex>
+
Обозначим за <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_{h = 1}^\infty  \limits}\frac{h}{2^h} = 2 </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>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>
 +
}}
  
<tex dpi = "160"> \frac{n}{2^n} = \frac{1}{2} \cdot \frac{n - 1}{2 ^{n - 1}} + \frac{1}{2^n} </tex>  
+
Подставляя в нашу формулу результат леммы, получаем <tex >n</tex> <tex dpi = "160">\cdot (\frac {d}{d - 1})^2 </tex> <tex>  \leqslant  4 \cdot n </tex> <tex>=O(n).</tex>
 +
}}
  
Получается <tex> S = \frac{1}{2} \cdot S + 1 </tex> (так как <tex>n >0</tex>). Получаем, что сумма ряда равна 2.
+
Псевдокод алгоритма:
Откуда и получаем оценку <tex> O(N) </tex>.
+
<code style="display:inline-block">
}}
+
'''function''' buldHeap():
Также можно обобщить на случай <tex> d-</tex> кучи <tex>(d- </tex> куча это куча в которой не 2 потомка, а <tex> d </tex> потомков). Все операции, которые делались c бинарной кучей, допустимы и для <tex>d</tex> - кучи. Посчитаю время построения <tex> d</tex> - кучи. В этом случае время работы не превзойдет  <tex dpi = "140">N \cdot d </tex> <tex dpi = "160" >   \cdot  {\sum_{i = 1}^H \limits}\frac{i}{d^i} .</tex>  
+
    '''for''' i = a.heapSize / 2 '''downto''' 0
 +
        siftDown(i)
 +
</code>
 +
 
 +
===Слияние двух куч===
 +
Даны две кучи <tex>a</tex> и <tex>b</tex>, размерами <tex>n</tex> и <tex>m</tex>, требуется объединить эти две кучи.  
 +
====Наивная реализация====
 +
Поочередно добавим все элементы из <tex>b</tex> в <tex>a</tex>. Время работы {{---}} <tex>O(m \log(n+m))</tex>.
 +
<code style="display:inline-block">
 +
'''function''' merge(a, b : '''Heap'''):
 +
    '''while''' b.heapSize > 0 
 +
        a.insert(b.extractMin())
 +
</code>
  
Здесь появился множитель <tex> d </tex> из-за того, что поиск минимума в sift_down происходит за <tex> d </tex>.
+
====Реализация с помощью построения кучи====
 +
Добавим все элементы кучи <tex>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(n + m)</tex>.  
  
Аналогичным образом посчитаю ряд <tex dpi = "160"> {\sum_{n = 1}^\infty \limits}\frac{n}{d^n} </tex>
+
<code style="display:inline-block">
 +
'''function''' merge(a, b : '''Heap'''):
 +
    '''for''' i = 0 '''to''' b.heapSize - 1   
 +
        a.heapSize = a.heapSize + 1
 +
        a[a.heapSize - 1] = b[i]
 +
    a.heapify()
 +
</code>  
  
<tex dpi = "160"> \frac{n}{d^n} = \frac{1}{d} \cdot \frac{n - 1}{d ^{n - 1}} + \frac{1}{d^n}. </tex>
+
===Поиск k-ого элемента (очень коряво расписано с неверными индексами)===
 +
Требуется найти <tex>k</tex>-ый по величине элемент в куче.
  
<tex dpi = "160">{\sum_{n = 1}^\infty  \limits}\frac{1}{d^n} </tex> это сумма бесконечной убывающей геометрической прогрессии ее сумма равна <tex dpi = "160">  
+
# Создаем новую кучу, в которой будем хранить пару <tex>\langle \mathtt{value}, \mathtt{index} \rangle</tex>, где <tex>\mathtt{value}</tex> {{---}} значение элемента, а <tex>\mathtt{index}</tex> {{---}} индекс элемента в основном массиве, и добавляем в нее корень кучи.
\frac{\frac{1}{d}}{1 - \frac{1}{d}} = \frac{1}{d - 1} </tex>  
+
# Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <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">  = \frac{d}{(d - 1)^2}. </tex>
+
Время работы алгоритма {{---}} <tex>O(k \log k)</tex>.
  
Подставляя в формулу для суммы получаю <tex > N </tex> <tex dpi = "160">\cdot (\frac {d}{d - 1})^2 </tex> <tex> 5 \cdot N </tex>.  
+
При <tex>n \lessapprox k \log k </tex> выгоднее запускать [[поиск k-ой порядковой статистики]].
 +
[[Файл:Min_heap_kth.png‎|thumb|center|650px|Пример при <tex>k = 5</tex>, красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]
  
Получаю время работы <tex> O(N) </tex>
+
== См. также ==
 +
* [[Биномиальная куча]]
 +
* [[Фибоначчиева куча]]
 +
* [[Левосторонняя куча]]
  
== Источники ==
+
== Источники информации ==
* [http://ru.wikipedia.org/wiki/Min-heap Двоичная куча — Wikipedia]
+
* [[wikipedia:ru:Двоичная куча|Википедия {{---}} Двоичная куча]]
* [http://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]
+
* [[wikipedia:ru:Очередь с приоритетом|Википедия {{---}} Очередь с приоритетом]]
 +
* [[wikipedia:en:Binary heap|Wikipedia {{---}} Binary heap]]
 +
* [[wikipedia:en:Priority queue|Wikipedia {{---}} Priority queue]]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:30, 4 сентября 2022

Определение

Определение:
Двоичная куча или пирамида (англ. Binary heap) — такое двоичное подвешенное дерево, для которого выполнены следующие три условия:
  • Значение в любой вершине не больше (если куча для минимума), чем значения её потомков.
  • На [math]i[/math]-ом слое [math]2^i[/math] вершин, кроме последнего. Слои нумеруются с нуля.
  • Последний слой заполнен слева направо (как показано на рисунке)
Пример кучи для минимума
Хранение кучи в массиве, красная стрелка — левый сын, зеленая — правый

Удобнее всего двоичную кучу хранить в виде массива [math]a[0..n-1][/math], у которого нулевой элемент, [math]a[0][/math] — элемент в корне, а потомками элемента [math]a[i][/math] являются [math]a[2i+1][/math] и [math]a[2i+2][/math]. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть [math]O(\log{n})[/math], где [math]n[/math] — количество узлов дерева.

Чаще всего используют кучи для минимума (когда предок не больше детей) и для максимума (когда предок не меньше детей).

Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за [math]O(\log{n})[/math]. Они являются частным случаем приоритетных очередей.

Базовые процедуры

Восстановление свойств кучи

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры [math] \mathrm {siftDown} [/math] (просеивание вниз) и [math] \mathrm {siftUp} [/math] (просеивание вверх).

siftDown

Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией [math] \mathrm {siftDown} [/math].

Работа процедуры: если [math]i[/math]-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами [math]i[/math]-й элемент с наименьшим из его сыновей, после чего выполняем [math] \mathrm {siftDown} [/math] для этого сына. Процедура выполняется за время [math]O(\log{n})[/math].

function siftDown(i : int):
    while 2 * i + 1 < a.heapSize     // heapSize — количество элементов в куче
        left = 2 * i + 1             // left — левый сын
        right = 2 * i + 2            // right — правый сын
        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

siftUp

Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией [math] \mathrm {siftUp} [/math].

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем [math] \mathrm {siftUp} [/math] для этого отца. Иными словами, слишком маленький элемент всплывает наверх. Процедура выполняется за время [math]O(\log{n})[/math].

function siftUp(i : int):
    while a[i] < a[(i - 1) / 2]     // i [math]==[/math] 0 — мы в корне
        swap(a[i], a[(i - 1) / 2])
        i = (i - 1) / 2

Извлечение минимального элемента

Выполняет извлечение минимального элемента из кучи за время [math]O(\log{n})[/math]. Извлечение выполняется в четыре этапа:

  1. Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
  2. Последний элемент копируется в корень, после чего удаляется из кучи.
  3. Вызывается [math] \mathrm {siftDown} [/math] для корня.
  4. Сохранённый элемент возвращается.
int extractMin():
    int min = a[0]
    a[0] = a[a.heapSize - 1]
    a.heapSize = a.heapSize - 1
    siftDown(0)
    return min

Добавление нового элемента

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

function insert(key : int):
    a.heapSize = a.heapSize + 1
    a[a.heapSize - 1] = key
    siftUp(a.heapSize - 1)

Построение кучи за O(n)

Определение:
[math]D[/math]-куча — это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно [math]d[/math] потомков.


Дан массив [math]a[0.. n - 1].[/math] Требуется построить [math]d[/math]-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива — сделать нулевой элемент массива корнем, а дальше по очереди добавить все его элементы в конец кучи и запускать от каждого добавленного элемента [math]\mathrm {siftUp}[/math]. Временная оценка такого алгоритма [math] O(n\log{n})[/math]. Однако можно построить кучу еще быстрее — за [math] O(n) [/math].

Представим, что в массиве хранится дерево ([math]a[0] - [/math] корень, а потомками элемента [math]a[i][/math] являются [math]a[di+1]...a[di+d][/math]). Сделаем [math] \mathrm {siftDown} [/math] для вершин, имеющих хотя бы одного потомка: от [math]\dfrac{n}{d}[/math] до [math]0[/math],— так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены.

Лемма:
На выходе получим искомую кучу.
Доказательство:
[math]\triangleright[/math]
До вызова [math] \mathrm {siftDown} [/math] для вершины, ее поддеревья являются кучами. После выполнения [math] \mathrm {siftDown} [/math] эта вершина с ее поддеревьями будут также являться кучей. Значит, после выполнения всех [math] \mathrm {siftDown} [/math] получится куча.
[math]\triangleleft[/math]
Лемма:
Время работы этого алгоритма [math] O(n) [/math].
Доказательство:
[math]\triangleright[/math]

Число вершин на высоте [math]h[/math] в куче из [math]n[/math] элементов не превосходит [math] \left \lceil \frac{n}{d^h} \right \rceil [/math]. Высота кучи не превосходит [math] \log_{d}n [/math]. Обозначим за [math] H [/math] высоту дерева, тогда время построения не превосходит

[math] \sum_{h = 1}^H \limits\frac{n}{d^h} \cdot d [/math] [math] \cdot h [/math] [math] = n \cdot d \cdot {\sum_{h = 1}^H \limits}\frac{h}{d^h}. [/math]

Докажем вспомогательную лемму о сумме ряда.

Лемма:
[math] {\sum_{h = 1}^\infty \limits}\frac{h}{d^h} = \frac{d}{(d - 1)^2} . [/math]
Доказательство:
[math]\triangleright[/math]

Обозначим за [math]s[/math] сумму ряда. Заметим, что [math] \frac{n}{d^n} = \frac{1}{d} \cdot \frac{n - 1}{d ^{n - 1}} + \frac{1}{d^n}. [/math]

[math]{\sum_{n = 1}^\infty \limits}\frac{1}{d^n}[/math] — это сумма бесконечной убывающей геометрической прогрессии, и она равна [math] \frac{\frac{1}{d}}{1 - \frac{1}{d}} = \frac{1}{d - 1}. [/math]

Получаем [math]s[/math] [math]=\frac{1}{d}[/math] [math]\cdot s +[/math] [math] \frac{1}{d - 1}. [/math] Откуда [math]s[/math] [math] = \frac{d}{(d - 1)^2}. [/math]
[math]\triangleleft[/math]
Подставляя в нашу формулу результат леммы, получаем [math]n[/math] [math]\cdot (\frac {d}{d - 1})^2 [/math] [math] \leqslant 4 \cdot n [/math] [math]=O(n).[/math]
[math]\triangleleft[/math]

Псевдокод алгоритма:

function buldHeap():
    for i = a.heapSize / 2 downto 0
        siftDown(i)

Слияние двух куч

Даны две кучи [math]a[/math] и [math]b[/math], размерами [math]n[/math] и [math]m[/math], требуется объединить эти две кучи.

Наивная реализация

Поочередно добавим все элементы из [math]b[/math] в [math]a[/math]. Время работы — [math]O(m \log(n+m))[/math].

function merge(a, b : Heap):
    while b.heapSize > 0  
        a.insert(b.extractMin())

Реализация с помощью построения кучи

Добавим все элементы кучи [math]b[/math] в конец массива [math]a[/math], после чего вызовем функцию построения кучи. Процедура выполняется за время [math]O(n + m)[/math].

function merge(a, b : Heap):
    for i = 0 to b.heapSize - 1  
        a.heapSize = a.heapSize + 1
        a[a.heapSize - 1] = b[i]
    a.heapify()

Поиск k-ого элемента (очень коряво расписано с неверными индексами)

Требуется найти [math]k[/math]-ый по величине элемент в куче.

  1. Создаем новую кучу, в которой будем хранить пару [math]\langle \mathtt{value}, \mathtt{index} \rangle[/math], где [math]\mathtt{value}[/math] — значение элемента, а [math]\mathtt{index}[/math] — индекс элемента в основном массиве, и добавляем в нее корень кучи.
  2. Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг [math]k - 1[/math] раз.
  3. В корне новой кучи будет находиться ответ.

Время работы алгоритма — [math]O(k \log k)[/math].

При [math]n \lessapprox k \log k [/math] выгоднее запускать поиск k-ой порядковой статистики.

Пример при [math]k = 5[/math], красные — уже удаленные из кучи элементы, зеленые находятся в куче, а голубые — еще не рассмотрены.

См. также

Источники информации