Бінарна купа - Вікіпедія

# Бінарна купа

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

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

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

    Parent(i)
        return

    Left(i)
        return 2i

    Right(i)
        return 2i + 1

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

.

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

.

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

Підтримку властивості купи можна здійснювати за допомогою процедури `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[largest]
     7     then
     8 if
     9     then Поміняти
     10         Max_Heapify(A,largest)

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

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

## [ред.] Побудова купи

За допомогою процедури `Max_Heapify` можно перетворити масив `A[1..n]`, де `n = length[A]`, у незростаючу купу. Всі елементи підмасиву є листами дерева, тому кожен з них можна вважати одноелементною купою, з якої можна почати процес побудови. Процедура `Build_Max_Heap` проходить по всім іншим вузлам і для кожного з них иконує процедуру `Max_Heapify`:

    Build_Max_Heap(A)

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

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

Для створення неспадної купи, необхідно замінити у третьому рядку алгоритма виклик `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` можливі три варіанти:

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

В залежності від варіанту властивість купи після зміни ключа треба відновлювати або процедурою `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"

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

##### Views

- Стаття
- Обговорення
- Поточна версія

##### Пошук

##### Іншими мовами

- English