Двійкова купа — Вікіпедія
Двійкова (min/max) купа | ||
---|---|---|
Тип | двійкове дерево/купа | |
Винайдено | 1964 | |
Винайшли | J. W. J. Williams | |
Обчислювальна складність у записі великого О | ||
Середня | Найгірша | |
Простір | O(n) | O(n) |
Пошук | O(n) | O(n) |
Вставляння | O(1) | O(log n) |
Видалення |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/220px-Max-Heap.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Min-heap.png/220px-Min-heap.png)
Двійкова купа[1] (англ. binary heap) — це структура даних, що є масивом, який можна розглядати як майже повне двійкове дерево. Кожен вузол цього дерева відповідає певному елементу масива. На всіх рівнях, крім, можливо останнього, дерево повністю заповнене (заповнений рівень — такий, що містить максимально можливу кількість вузлів). Останній рівень заповнюється послідовно зліва направо до тих пір, доки в масиві не закінчаться елементи.
Для масиву A у корені дерева знаходиться елемент A[1]. Далі дерево будується за наступним принципом: якщо якомусь вузлу відповідає індекс i, то індекс його батьківського вузла обчислюється за допомогою процедури Parent(i), індекс лівого дочірнього вузла — за допомогою процедури Left(i), а індекс правого дочірнього вузла — за допомогою процедури Right(i):
Parent(i) return Left(i) return Right(i) return
Розглядають два види бінарних куп: неспадні і незростаючі. В обох видах значення, що розташовані у вузлах купи, задовільняють властивості купи (англ. 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 and 4 then 5 else 6 if and 7 then 8 if 9 then Swap 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))
Час роботи процедури є .
Процедура черги з пріоритетами 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 виконується за , процедури Insert, Extract_Max, Change_Key виконуються за .
- ↑ Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
- Алгоритм сортування купою був запропонований Вільямсом (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).
![]() | Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її. |