Двійкова купа

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

Max_Heapify(A,i)

 1 ${\displaystyle l\gets \;Left(i)}$
 2 ${\displaystyle r\gets \;Right(i)}$
 3 if ${\displaystyle l\leq \;heap\_size[A]}$ and ${\displaystyle A[l]>A[i]}$
 4     then ${\displaystyle largest\gets \;l}$
 5     else ${\displaystyle largest\gets \;i}$
 6 if ${\displaystyle r\leq \;heap\_size[A]}$ and ${\displaystyle A[r]>A[largest]}$
 7     then ${\displaystyle largest\gets \;r}$
 8 if ${\displaystyle largest\neq \;i}$
 9     then Swap ${\displaystyle A[i]\leftrightarrow \;A[largest]}$
 10         Max_Heapify(A,largest)

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

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

За допомогою процедури Max_Heapify можна перетворити масив A[1..n], де n = length[A], у незростаючу купу. Всі елементи підмасиву ${\displaystyle A[(\lfloor \;n/2\rfloor \;+1)..n]}$ є листами дерева, тому кожен з них можна вважати одноелементною купою, з якої можна почати процес побудови. Процедура Build_Max_Heap проходить по всіх інших вузлах і для кожного з них виконує процедуру Max_Heapify:

Build_Max_Heap(A)

1 ${\displaystyle heap\_size[A]\gets \;length[A]}$
2 for ${\displaystyle i\gets \;\lfloor \;length[A]/2\rfloor }$ downto 1
3     do Max_Heapify(A,i)

По завершенню роботи процедури, масив A організується в незростаючу купу. Час роботи процедури Build_Max_Heap можна записати так:

${\displaystyle 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)}$

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

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

Heapsort(A)
1 Build_Max_Heap(A)
2 for ${\displaystyle i\gets \;length[A]}$ downto 2
3     do Поміняти ${\displaystyle A[1]\leftrightarrow \;A[i]}$
4        ${\displaystyle heap\_size[A]\gets \;heap\_size[A]-1}$
5        Max_Heapify(A,1)

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

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

Un_Max_Heapify(A,i)
1 if i = 1
2    then return
3 if A[Parent(i)]<A[i]
4    then Поміняти ${\displaystyle A[Parent(i)]\leftrightarrow \;A[i]}$
5         Un_Max_Heapify(A,Parent(i))

Час роботи процедури є ${\displaystyle O(logn)}$.

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

Insert(A,x)
1 ${\displaystyle heap\_size[A]\gets \;heap\_size[A]+1}$
2 ${\displaystyle A[heap\_size[A]]\gets \;x}$
3 Un_Max_Heapify(A,heap_size[A])

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

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

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

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

У процедурі Change_Key можливі три варіанти:

1. ключ елемента збільшився
2. ключ елемента зменшився
3. ключ елемента не змінився

В залежності від варіанту властивість купи після зміни ключа треба відновлювати або процедурою Un_Max_Heapify або процедурою Max_Heapify:

Change_Key(A,i,k)

1 ${\displaystyle old\_key\gets \;A[i]}$
2 ${\displaystyle A[i]\gets \;k}$
3 if k>old_key
4     then Un_Max_Heapify(A,i)
5     elseif k < old_key
6            Max_Heapify(A,i)

• Алгоритм сортування купою був запропонований Вільямсом (Williams, J. W. J. (1964). Algorithm 232 - Heapsort. Communications of the ACM 7 (6): 347–348. doi:10.1145/512274.512284.). Він також описав, що за допомогою купи можна реалізувати чергу з пріоритетом.
• Процедура Build_Max_Heap була розроблена Флойдом (Robert W. Floyd. Algorithm 245 (TREESORT). Communications of the ACM, 7:701, 1964).
• Детальний опис бінарної купи, можна знайти у книзі Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3). К.І.С. с. 168–171. ISBN 978-617-684-239-2.

• Купа (структура даних)