Перегляд вихідного коду сторінки Двійкова купа

{{Картка:Структура даних
|name=Двійкова (min/max) купа
|type=двійкове дерево/купа
|space_avg=O(n)
|space_worst=O(n)
|search_avg=O(n)
|search_worst=O(n)
|insert_worst=O(log n)
|insert_avg=O(1)
<!--|delete_avg=
|delete_worst=O(log n)-->
|delete_min_avg=O(log n)
|delete_min_worst=O(log n)
|invented_by=J. W. J. Williams
|invented_year=1964
|find_min_avg=O(1)
|find_min_worst=O(1)}}
[[File:Max-Heap.svg|thumb|right|Приклад повної двійкової максимальної купи. Наведено її представлення у вигляді масива.]]
[[File:Min-heap.png|thumb|right|Приклад повної двійкової мінімальної купи.]]
'''Двійкова купа'''<ref name="mit">{{CLRS|chapter=Розділ 6.1: Купи}}</ref> ({{lang-en|binary heap}})&nbsp;— це [[структура даних]], що є [[Масив (структура даних)|масивом]], який можна розглядати як майже повне [[бінарне дерево|двійкове дерево]]. Кожен вузол цього дерева відповідає певному елементу масива. На всіх рівнях, крім, можливо останнього, дерево повністю заповнене (заповнений рівень&nbsp;— такий, що містить максимально можливу кількість вузлів). Останній рівень заповнюється послідовно зліва направо до тих пір, доки в масиві не закінчаться елементи.

Для масиву <tt>A</tt> у корені дерева знаходиться елемент <tt>A[1]</tt>. Далі дерево будується за наступним принципом: якщо якомусь вузлу відповідає індекс <tt>''i''</tt>, то індекс його батьківського вузла обчислюється за допомогою процедури <tt>Parent(''i'')</tt>, індекс лівого дочірнього вузла&nbsp;— за допомогою процедури <tt>Left(''i'')</tt>, а індекс правого дочірнього вузла&nbsp;— за допомогою процедури <tt>Right(''i'')</tt>:

 Parent(i)
     '''return''' <math>\lfloor\;i/2\rfloor</math>
 
 Left(i)
     '''return''' <math>2i</math>
 
 Right(i)
     '''return''' <math>2i+1</math> 
Розглядають два види бінарних куп: неспадні і незростаючі. В обох видах значення, що розташовані у вузлах купи, задовільняють '''властивості купи''' ({{lang-en|heap property}}).
'''Властивісь незростаючої купи''' ({{lang-en|max-heap property}}) полягає в тому, що для кожного вузла крім кореневого виконується нерівність:

:<math>A[Parent(i)] \geqslant A[i]</math>.

Іншими словами, значення вузла не перевищує значення батьківського вузла. Таким чином найбільший елемент знаходиться в корені дерева.
Принцип побудови '''неспадної купи''' ({{lang-en|min-heap}}) протилежний. '''Властивість неспадної купи''' ({{lang-en|min-heap property}}) полягає в тому, що кожен елемент крім кореневого є ''неменшим'' за свій батьківський елемент:

:<math>A[Parent(i)] \leqslant A[i]</math>.

== Підтримка властивостей купи ==
Підтримку властивості купи можна здійснювати за допомогою процедури <tt>Max_Heapify</tt> (для незростаючих бінарних куп). На вхід подається масив <tt>A</tt> й індекс <tt>i</tt> цього масиву. При виклику процедури <tt>Max_Heapify</tt> припускається, що бінарні дерева, коренями яких є елементи <tt>Left(i)</tt> і <tt>Right(i)</tt> є незростаючими купами, але сам елемент <tt>A[i]</tt> може бути меншим за його дочірні елементи і тим самим порушувати властивість незростаючої купи. Процедура <tt>Max_Heapify</tt> спускає значення елемента <tt>A[i]</tt> вниз по купі до тих пір, доки дерево в якому цей елемент буде коренем не стане незростаючою бінарною купою:

 Max_Heapify(''A'',''i'')
 
  1 <math>l\gets \;Left(i)</math>
  2 <math>r\gets \;Right(i)</math>
  3 '''if''' <math>l \le \;heap\_size[A]</math> '''and''' <math>A[l]>A[i]</math>
  4     '''then''' <math>largest \gets\; l</math>
  5     '''else''' <math>largest \gets\; i</math>
  6 '''if''' <math>r \le \;heap\_size[A]</math> '''and''' <math>A[r]>A[largest]</math>
  7     '''then''' <math>largest \gets\; r</math>
  8 '''if''' <math>largest \ne\;i</math>
  9     '''then''' Swap <math>A[i]\leftrightarrow\;A[largest]</math>
  10         Max_Heapify(''A'',''largest'')

Час роботи процедури в найгіршому випадку пропорційний висоті купи. Якщо купа складається з <tt>n</tt> елементів, то її висота <tt>log<sub>2</sub>(n)</tt> . Тому оцінка часу роботи одного виклику <tt>Max_Heapify</tt> є <tt>O(log n)</tt>.

Для підтримки властивості неспадної бінарної купи можна скористатись процедурою <tt>Min_Heapify</tt>. Вона повністю подібна до <tt>Max_Heapify</tt>, тільки в рядках 3 і 6 алгоритму знак «>» треба замінити на «<».

== Побудова купи ==
За допомогою процедури <tt>Max_Heapify</tt> можна перетворити масив <tt>A[1..n]</tt>, де <tt>n = ''length''[A]</tt>, у незростаючу купу. Всі елементи підмасиву <math>A[(\lfloor\;n/2\rfloor\;+1)..n]</math> є [[лист]]ами дерева, тому кожен з них можна вважати одноелементною купою, з якої можна почати процес побудови. Процедура <tt>Build_Max_Heap</tt> проходить по всіх інших вузлах і для кожного з них виконує процедуру <tt>Max_Heapify</tt>:
 
 Build_Max_Heap(''A'')
 
 1 <math>heap\_size[A] \gets\; length[A] </math>
 2 '''for''' <math>i \gets\;\lfloor\;length[A]/2\rfloor</math> '''downto''' 1
 3     '''do''' Max_Heapify(''A'',''i'')
 
По завершенню роботи процедури, масив <tt>A</tt> організується в незростаючу купу. Час роботи процедури <tt>Build_Max_Heap</tt> можна записати так:

: <math>O\left(n\sum_{h=0}^{\lfloor\;\log_{2}n\rfloor}\frac{h}{2^h}\right) = O\left(n\sum_{h=0}^{\infty}\frac{h}{2^h}\right) = O(n)</math>

Для створення неспадної купи, необхідно замінити у третьому рядку алгоритму виклик <tt>Max_Heapify</tt> на <tt>Min_Heapify</tt>.

== Алгоритм впорядкування купою ==
Робота алгоритму сортування купою починається з виклику процедури <tt>Build_Max_H</tt>, за допомогою якої з початкового масиву <tt>A[1..n]</tt> створюється незростаюча купа. Далі послідовно з купи виймається найбільший елемент, який міняють з останнім в купі. Після кожного обміну розмір купи зменшують на одиницю. В кінці отримують повністю відсортований неспадний масив:

 Heapsort(''A'')
 1 Build_Max_Heap(''A'')
 2 '''for''' <math>i\gets\;length[A]</math> '''downto''' 2
 3     '''do''' Поміняти <math>A[1]\leftrightarrow\;A[i]</math>
 4        <math>heap\_size[A]\gets\;heap\_size[A]-1</math>
 5        Max_Heapify(''A'',1)

Час роботи процедури <tt>Heapsort</tt> рівний <tt>O(n log n)</tt>, оскільки всього потрібно <tt>n-1</tt> викликів <tt>Max_Heapify</tt>, кожен з яких працює за <tt>O(log n)</tt>.

== Черга з пріоритетами ==
{{main|Черга з пріоритетом}}

Для того, щоб реалізувати на купі операції черги з пріоритетами використовують ще одну допоміжну процедуру <tt>Un_Max_Heapify(''A'',''i'')</tt>. Ця процедура підтримує властивість незростаючої купи (аналогічно <tt>Un_Min_Heapify(''A'',''i'')</tt> для неспадної купи), за умови якщо властивість купи порушується в елементі з індексом <tt>''i''</tt>&nbsp;— він може бути більшим за батьківський елемент. При цьому припускається, що в усіх інших елементах властивість виконується і батьківський елемент i-го більший кожного з нащадків i-го елемента. Процедура «піднімає» елемент угору по дереву доти, доки він не перестане порушувати властивість купи:

 Un_Max_Heapify(''A'',''i'')
 1 '''if''' i = 1
 2    '''then return'''
 3 '''if''' A[Parent(i)]<A[i]
 4    '''then''' Поміняти <math>A[Parent(i)]\leftrightarrow\;A[i]</math>
 5         Un_Max_Heapify(''A'',Parent(i))

Час роботи процедури є <math>O(log n)</math>.

Процедура черги з пріоритетами <tt>Insert</tt> реалізується таким чином: в кінець купи дописується один елемент (при цьому розмір купи збільшується на 1), потім за допомогою <tt>Un_Max_Heapify</tt> цей елемент піднімається на необхідний рівень.

 Insert(''A'',''x'')
 1 <math>heap\_size[A]\gets\;heap\_size[A]+1</math>
 2 <math>A[heap\_size[A]]\gets\;x</math>
 3 Un_Max_Heapify(''A'',heap_size[A])

Максимальний елемент знаходиться в першому елементі купи, тому процедура <tt>Maximum</tt> реалізується тривіально:

 Maximum(''A'')
 1 '''if''' heap_size[A] = 0
 2    '''then''' Помилка "Черга пуста"
 3    '''else return''' A[1]

В процедурі <tt>Extract_Max</tt> розмір купи зменшується на 1, останній елемент записується на місце першого (при цьому порушується властивість купи). Властивість купи відновлюється процедурою <tt>Max_Heapify</tt>.

 Extract_Max(''A'')
 1 '''if''' heap_size[A] = 0
 2    '''then''' Помилка "Черга пуста"
 3 <math>max\gets\;A[1]</math>
 4 <math>A[1]\gets\;A[heap\_size[A]]</math>
 5 <math>heap\_size[A]\gets\;heap\_size[A]-1</math>
 6 '''if''' heap_size[A] > 0
 7    '''then''' Max_Heapify(''A'',1)
 8 '''return''' ''max''

У процедурі <tt>Change_Key</tt> можливі три варіанти:
# ключ елемента збільшився
# ключ елемента зменшився
# ключ елемента не змінився
В залежності від варіанту властивість купи після зміни ключа треба відновлювати або процедурою <tt>Un_Max_Heapify</tt> або процедурою <tt>Max_Heapify</tt>:

 Change_Key(''A'',''i'',''k'')
 
 1 <math>old\_key\gets\;A[i]</math>
 2 <math>A[i]\gets\;k</math>
 3 '''if''' k>old_key
 4     '''then''' Un_Max_Heapify(''A'',''i'')
 5     '''elseif''' k < old_key
 6            Max_Heapify(''A'',''i'')

=== Асимптотична складність операцій ===
Процедура <tt>Maximum</tt> виконується за <math>\mathit{O(1)}</math>, процедури <tt>Insert, Extract_Max, Change_Key</tt> виконуються за <math>\mathit{O(\log_2 n)}</math>.

== Примітки ==
{{reflist}}

== Джерела ==
* {{CLRS|chapter=Розділ 6.1: Купи}}
* Алгоритм сортування купою був запропонований Вільямсом ({{Citation |first=J. W. J. |last=Williams |author-link=J. W. J. Williams |title=Algorithm 232 - Heapsort |year=1964 |journal=[[Communications of the ACM]] |volume=7 |issue=6 |pages=347–348 |doi= 10.1145/512274.512284}}). Він також описав, що за допомогою купи можна реалізувати [[Черга з пріоритетом|чергу з пріоритетом]]. 
* Процедура ''Build_Max_Heap'' була розроблена Флойдом (Robert W. Floyd. Algorithm 245 (TREESORT). ''Communications of the ACM'', 7:701, 1964).

{{Дерева (інформатика)}}

{{Compu-stub}}

[[Категорія:Структури даних]]
[[Категорія:Алгоритми сортування]]