Бінарна купа

Матеріал з Вікіпедії — вільної енциклопедії.

Бінарна купа (англ. binary heap) — це структура даних, що є масивом, який можна розглядати як майже повне бінарне дерево. Кожен вузол цього дерева відповідає певному елементу масиву. На всіх рівнях, крім, можливо останнього, дерево повністю заповнене (заповнений рівень — такий, що містить максимально можливу кількість вузлів). Останній рівень заповнюється послідовно зліва направо до тих пір, доки в масиві не закінчатся елементи.

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

Parent(i)
    return 

Left(i)
    return  $2 i$ 

Right(i)
    return  $2 i + 1$

Розглядають два види бінарних куп: неспадні і незростаючі. В обох видах значення, що розташовані у вузлах купи, задовільняють властивості купи (англ. heap property). Властивісь незростаючої купи (англ. max-heap property) полягає в тому, що для кожного вузла крім кореневого виконується нерівність:

$A[Parent(i)] \ge\; A[i]$ .

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

$A[Parent(i)] \le\; A[i]$ .

Зміст

1 Підтримка властивостей купи
2 Побудова купи
3 Алгоритм впорядкування купою
4 Черга з пріорітетами
- 4.1 Асимптотична складність операцій
5 Література

[ред.] Підтримка властивостей купи

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


Max_Heapify(A,i)

 1 
 2 
 3 if  і  $A [l] > A [i]$ 
 4     then 
 5     else 
 6 if  і  $A [r] > A [l a r g e s t]$ 
 7     then 
 8 if 
 9     then Поміняти 
 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], у незростаючу купу. Всі елементи підмасиву $A[(\lfloor\;n/2\rfloor\;+1)..n]$ є листами дерева, тому кожен з них можна вважати одноелементною купою, з якої можна почати процес побудови. Процедура Build_Max_Heap проходить по всім іншим вузлам і для кожного з них иконує процедуру Max_Heapify:


Build_Max_Heap(A)

1 
2 for  downto 1
3     do Max_Heapify(A,i)

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

$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  downto 2
3     do Поміняти 
4        
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 Поміняти 
5         Un_Max_Heapify(A,Parent(i))

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

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


Insert(A,x)
1 
2 
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 
4 
5 
6 if heap_size[A] > 0
7    then Max_Heapify(A,1)
8 return max

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

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

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


Change_Key(A,i,k)

1 
2 
3 if k>old_key
4     then Un_Max_Heapify(A,i)
5     elseif k<old_key
6            Max_Heapify(A,i)

[ред.] Асимптотична складність операцій

Процедура Maximum виконується за O(1), процедури Insert, Extract_Max, Change_Key виконуються за O(log n).

[ред.] Література

Алгоритм сортування купою був запропонований Вільямсом (J. W. J. Williams. Algorithm 232 (HEASPORT). Communications of the ACM, 7:347-348, 1964), який також описав, що за допомогою купи можна реалізувати чергу з пріорітетами. Процедура Build_Max_Heap була розроблена Флойдом (Robert W. Floyd. Algorithm 245 (TREESORT). Communications of the ACM, 7:701, 1964).

Детальний опис бінарної купи, можна знайти в книзі "Алгоритми, побудова і аналіз" Т. Кормен, Ч. Лейзерсон, Р. Рівест, К. Штайн (Thomas H. Cormen, Charles E. Leiserson, Roland L.Rivest, Clifford Stein, "Introduction to ALGORITHMS" second edition, The MIT Press, Cambridge, Massachusetts, London)

Отримано від "http://uk.wikipedia.org../../../%D0%B1/%D1%96/%D0%BD/%D0%91%D1%96%D0%BD%D0%B0%D1%80%D0%BD%D0%B0_%D0%BA%D1%83%D0%BF%D0%B0.html"

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