Редактирование: Двоичная куча

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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|Пример кучи для минимума]]
+
 
[[Файл:Min_heap_array.png‎|thumb|325px|Хранение кучи в массиве, красная стрелка {{---}} левый сын, зеленая {{---}} правый]]
+
[[Файл:Heap.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: Строка 24:
 
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
 
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
 
и <tex> \mathrm {siftUp} </tex> (просеивание вверх).  
 
и <tex> \mathrm {siftUp} </tex> (просеивание вверх).  
 
====siftDown====
 
 
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.
 
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.
 
 
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
 
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
Процедура выполняется за время <tex>O(\log{n})</tex>.
+
Процедура выполняется за время <tex>O(\log{N})</tex>.
 
+
====siftDown====
<code style="display:inline-block">
+
<code>
 
  '''function''' siftDown(i : '''int'''):
 
  '''function''' siftDown(i : '''int'''):
     '''while''' 2 * i + 1 < a.heapSize    <font color = "green">// heapSize {{---}} количество элементов в куче</font>
+
     '''while''' 2 * i + 1 < A.heapSize    <font color = "green">// <tex>heapSize</tex> {{---}} количество элементов в куче</font>
         left = 2 * i + 1             <font color = "green">// left {{---}} левый сын</font>
+
         left = A[2 * i + 1]    <font color = "green">// left {{---}} левый сын</font>
         right = 2 * i + 2           <font color = "green">// right {{---}} правый сын</font>
+
         '''if''' 2 * i + 2 < A.heapSize '''and''' A[2 * i + 2] <= left    <font color = "green">// A[2 * i + 2] {{---}} правый сын</font>
        j = left
+
            swap(A[2 * i + 2], A[i])
        '''if''' right < a.heapSize '''and''' a[right] < a[left]
+
             i = 2 * i + 2
             j = right
+
         '''else if''' A[2 * i + 1] < A[i]
         '''if''' a[i] <= a[j]
+
             swap(A[2 * i + 1], A[i])
             '''break'''
+
            i = 2 * i + 1
        swap(a[i], a[j])
+
        '''else'''
        i = j
+
            break
 
</code>
 
</code>
 
 
====siftUp====
 
====siftUp====
 
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.
 
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.
  
 
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>
 
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>
для этого отца. Иными словами, слишком маленький элемент всплывает наверх.
+
для этого отца. Иными словами, слишком большой элемент всплывает наверх.
Процедура выполняется за время <tex>O(\log{n})</tex>.  
+
Процедура выполняется за время <tex>O(\log{N})</tex>.  
<code style="display:inline-block">
+
<code>
 
  '''function''' siftUp(i : '''int'''):
 
  '''function''' siftUp(i : '''int'''):
     '''while''' a[i] < a[(i - 1) / 2]    <font color = "green">// i <tex>==</tex> 0 {{---}} мы в корне</font>
+
     '''while''' A[i] < A[(i - 1) / 2]    <font color = "green">// i == 0 {{---}} мы в корне</font>
         swap(a[i], a[(i - 1) / 2])
+
         swap(A[i], A[(i - 1) / 2])
 
         i = (i - 1) / 2
 
         i = (i - 1) / 2
 
</code>
 
</code>
Строка 58: Строка 56:
 
===Извлечение минимального элемента===
 
===Извлечение минимального элемента===
  
Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{n})</tex>.
+
Выполняет извлечение минимального элемента из кучи за время <tex>O(\log{N})</tex>.
 
Извлечение выполняется в четыре этапа:
 
Извлечение выполняется в четыре этапа:
 
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
 
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
Строка 65: Строка 63:
 
# Сохранённый элемент возвращается.
 
# Сохранённый элемент возвращается.
  
 +
<code>
 
  '''int''' extractMin():
 
  '''int''' extractMin():
    '''int''' min = a[0]
+
  '''int''' min = A[0]
    a[0] = a[a.heapSize - 1]
+
  A[0] = A[A.heap_size - 1]
    a.heapSize = a.heapSize - 1
+
  A.heap_size = A.heap_size - 1
    siftDown(0)
+
  siftDown(0)
    '''return''' min
+
  '''return''' min
 +
</code>
  
 
===Добавление нового элемента===
 
===Добавление нового элемента===
  
Выполняет добавление элемента в кучу за время <tex>O(\log{n})</tex>.
+
Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
 
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \mathrm {siftUp} </math>.
 
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \mathrm {siftUp} </math>.
  
<code style="display:inline-block">
+
<code>
 
  '''function''' insert(key : '''int'''):
 
  '''function''' insert(key : '''int'''):
    a.heapSize = a.heapSize + 1
+
  A.heap_size = A.heap_size + 1
    a[a.heapSize - 1] = key
+
  A[A.heap_size - 1] = key
    siftUp(a.heapSize - 1)
+
  siftUp(A.heap_size - 1)
 
</code>
 
</code>
  
===Построение кучи за O(n) ===
+
==Построение кучи за O(N) ==
 
{{Определение | definition =
 
{{Определение | definition =
'''<tex>D</tex>-куча''' {{---}} это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно <tex>d</tex> потомков.  
+
'''<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.. N - 1].</tex> Требуется построить <tex>D</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива - по очереди добавить все его элементы (сделать <tex> \mathrm {siftDown} </tex> для каждого). Временная оценка такого алгоритма <tex> O(N\log{N})</tex>. Однако можно построить кучу еще быстрее — за <tex> O(N) </tex>.  
 
+
Представим, что в массиве хранится дерево (<tex>A[0] - </tex>  корень, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i+1]...A[2i+D]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка, начиная с конца (от <tex> n - 1</tex> до <tex>0</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= На выходе получим искомую кучу.  
 
|statement= На выходе получим искомую кучу.  
|proof= До вызова <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами. После выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей.  Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
+
|proof= При вызове <tex> \mathrm {siftDown} </tex> для вершины, ее поддеревья являются кучами, после выполнения <tex> \mathrm {siftDown} </tex> эта вершина с ее поддеревьями будут также являться кучей.  Значит, после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
 
}}
 
}}
 
{{Лемма
 
{{Лемма
|statement= Время работы этого алгоритма <tex> O(n) </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> высоту дерева, тогда время построения не превосходит
+
|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>
+
<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>  
+
|statement= <tex dpi = "160"> {\sum_{h = 1}^\infty  \limits}\frac{h}{D^h} = \frac{D}{(D - 1)^2} . </tex>  
 
|proof=
 
|proof=
  Обозначим за <tex>s</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"> \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">  
 
<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>  
+
\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>
+
Получаем  <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 >n</tex> <tex dpi = "160">\cdot (\frac {d}{d - 1})^2 </tex> <tex>  \leqslant  4 \cdot n </tex> <tex>=O(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>
 
}}
 
}}
 
Псевдокод алгоритма:
 
<code style="display:inline-block">
 
'''function''' buldHeap():
 
    '''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>b</tex> в конец массива <tex>a</tex>, после чего вызовем функцию построения кучи. Процедура выполняется за время <tex>O(n + m)</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>
 
 
===Поиск k-ого элемента (очень коряво расписано с неверными индексами)===
 
Требуется найти <tex>k</tex>-ый по величине элемент в куче.
 
 
# Создаем новую кучу, в которой будем хранить пару <tex>\langle \mathtt{value}, \mathtt{index} \rangle</tex>, где <tex>\mathtt{value}</tex> {{---}} значение элемента, а <tex>\mathtt{index}</tex> {{---}} индекс элемента в основном массиве, и добавляем в нее корень кучи.
 
# Возьмем корень новой кучи и добавим её детей из основной кучи, после чего удалим корень. Проделаем этот шаг <tex>k - 1</tex> раз.
 
# В корне новой кучи будет находиться ответ.
 
 
Время работы алгоритма {{---}} <tex>O(k \log k)</tex>.
 
 
При <tex>n \lessapprox k \log k </tex> выгоднее запускать [[поиск k-ой порядковой статистики]].
 
[[Файл:Min_heap_kth.png‎|thumb|center|650px|Пример при <tex>k = 5</tex>, красные {{---}} уже удаленные из кучи элементы, зеленые находятся в куче, а голубые {{---}} еще не рассмотрены.]]
 
 
== См. также ==
 
* [[Биномиальная куча]]
 
* [[Фибоначчиева куча]]
 
* [[Левосторонняя куча]]
 
  
 
== Источники информации ==
 
== Источники информации ==
Строка 172: Строка 126:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: