Двійкова купа (англ. binary heap) — це структура даних, що є масивом, який можна розглядати як майже повне двійкове дерево. Кожен вузол цього дерева відповідає певному елементу масива. На всіх рівнях, крім, можливо останнього, дерево повністю заповнене (заповнений рівень — такий, що містить максимально можливу кількість вузлів). Останній рівень заповнюється послідовно зліва направо до тих пір, доки в масиві не закінчаться елементи.
Двійкова (min/max) купа | ||
---|---|---|
Тип | двійкове дерево/купа | |
Винайдено | 1964 | |
Винайшли | J. W. J. Williams | |
Обчислювальна складність у записі великого О | ||
Середня | Найгірша | |
Простір | O(n) | O(n) |
Пошук | O(n) | O(n) |
Вставляння | O(1) | O(log n) |
Видалення |
Для масиву 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 .
Джерела
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- Алгоритм сортування купою був запропонований Вільямсом ( (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).
Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Dvijkova kupa angl binary heap ce struktura danih sho ye masivom yakij mozhna rozglyadati yak majzhe povne dvijkove derevo Kozhen vuzol cogo dereva vidpovidaye pevnomu elementu masiva Na vsih rivnyah krim mozhlivo ostannogo derevo povnistyu zapovnene zapovnenij riven takij sho mistit maksimalno mozhlivu kilkist vuzliv Ostannij riven zapovnyuyetsya poslidovno zliva napravo do tih pir doki v masivi ne zakinchatsya elementi Dvijkova min max kupaTip dvijkove derevo kupaVinajdeno 1964Vinajshli J W J WilliamsObchislyuvalna skladnist u zapisi velikogo OSerednya NajgirshaProstir O n O n Poshuk O n O n Vstavlyannya O 1 O log n VidalennyaPriklad povnoyi dvijkovoyi maksimalnoyi kupi Navedeno yiyi predstavlennya u viglyadi masiva Priklad povnoyi dvijkovoyi minimalnoyi kupi Dlya masivu A u koreni dereva znahoditsya element A 1 Dali derevo buduyetsya za nastupnim principom yaksho yakomus vuzlu vidpovidaye indeks i to indeks jogo batkivskogo vuzla obchislyuyetsya za dopomogoyu proceduri Parent i indeks livogo dochirnogo vuzla za dopomogoyu proceduri Left i a indeks pravogo dochirnogo vuzla za dopomogoyu proceduri Right i Parent i return i 2 displaystyle lfloor i 2 rfloor Left i return 2i displaystyle 2i Right i return 2i 1 displaystyle 2i 1 Rozglyadayut dva vidi binarnih kup nespadni i nezrostayuchi V oboh vidah znachennya sho roztashovani u vuzlah kupi zadovilnyayut vlastivosti kupi angl heap property Vlastivis nezrostayuchoyi kupi angl max heap property polyagaye v tomu sho dlya kozhnogo vuzla krim korenevogo vikonuyetsya nerivnist A Parent i A i displaystyle A Parent i geqslant A i Inshimi slovami znachennya vuzla ne perevishuye znachennya batkivskogo vuzla Takim chinom najbilshij element znahoditsya v koreni dereva Princip pobudovi nespadnoyi kupi angl min heap protilezhnij Vlastivist nespadnoyi kupi angl min heap property polyagaye v tomu sho kozhen element krim korenevogo ye nemenshim za svij batkivskij element A Parent i A i displaystyle A Parent i leqslant A i Pidtrimka vlastivostej kupiPidtrimku vlastivosti kupi mozhna zdijsnyuvati za dopomogoyu proceduri Max Heapify dlya nezrostayuchih binarnih kup Na vhid podayetsya masiv A j indeks i cogo masivu Pri vikliku proceduri Max Heapify pripuskayetsya sho binarni dereva korenyami yakih ye elementi Left i i Right i ye nezrostayuchimi kupami ale sam element A i mozhe buti menshim za jogo dochirni elementi i tim samim porushuvati vlastivist nezrostayuchoyi kupi Procedura Max Heapify spuskaye znachennya elementa A i vniz po kupi do tih pir doki derevo v yakomu cej element bude kornem ne stane nezrostayuchoyu binarnoyu kupoyu Max Heapify A i 1 l Left i displaystyle l gets Left i 2 r Right i displaystyle r gets Right i 3 if l heap size A displaystyle l leq heap size A and A l gt A i displaystyle A l gt A i 4 then largest l displaystyle largest gets l 5 else largest i displaystyle largest gets i 6 if r heap size A displaystyle r leq heap size A and A r gt A largest displaystyle A r gt A largest 7 then largest r displaystyle largest gets r 8 if largest i displaystyle largest neq i 9 then Swap A i A largest displaystyle A i leftrightarrow A largest 10 Max Heapify A largest Chas roboti proceduri v najgirshomu vipadku proporcijnij visoti kupi Yaksho kupa skladayetsya z n elementiv to yiyi visota log2 n Tomu ocinka chasu roboti odnogo vikliku Max Heapify ye O log n Dlya pidtrimki vlastivosti nespadnoyi binarnoyi kupi mozhna skoristatis proceduroyu Min Heapify Vona povnistyu podibna do Max Heapify tilki v ryadkah 3 i 6 algoritmu znak gt treba zaminiti na lt Pobudova kupiZa dopomogoyu proceduri Max Heapify mozhna peretvoriti masiv A 1 n de n length A u nezrostayuchu kupu Vsi elementi pidmasivu A n 2 1 n displaystyle A lfloor n 2 rfloor 1 n ye listami dereva tomu kozhen z nih mozhna vvazhati odnoelementnoyu kupoyu z yakoyi mozhna pochati proces pobudovi Procedura Build Max Heap prohodit po vsih inshih vuzlah i dlya kozhnogo z nih vikonuye proceduru Max Heapify Build Max Heap A 1 heap size A length A displaystyle heap size A gets length A 2 for i length A 2 displaystyle i gets lfloor length A 2 rfloor downto 1 3 do Max Heapify A i Po zavershennyu roboti proceduri masiv A organizuyetsya v nezrostayuchu kupu Chas roboti proceduri Build Max Heap mozhna zapisati tak O n h 0 log2 n h2h O n h 0 h2h O n 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 Dlya stvorennya nespadnoyi kupi neobhidno zaminiti u tretomu ryadku algoritmu viklik Max Heapify na Min Heapify Algoritm vporyadkuvannya kupoyuRobota algoritmu sortuvannya kupoyu pochinayetsya z vikliku proceduri Build Max H za dopomogoyu yakoyi z pochatkovogo masivu A 1 n stvoryuyetsya nezrostayucha kupa Dali poslidovno z kupi vijmayetsya najbilshij element yakij minyayut z ostannim v kupi Pislya kozhnogo obminu rozmir kupi zmenshuyut na odinicyu V kinci otrimuyut povnistyu vidsortovanij nespadnij masiv Heapsort A 1 Build Max Heap A 2 for i length A displaystyle i gets length A downto 2 3 do Pominyati A 1 A i displaystyle A 1 leftrightarrow A i 4 heap size A heap size A 1 displaystyle heap size A gets heap size A 1 5 Max Heapify A 1 Chas roboti proceduri Heapsort rivnij O n log n oskilki vsogo potribno n 1 viklikiv Max Heapify kozhen z yakih pracyuye za O log n Cherga z prioritetamiDokladnishe Cherga z prioritetom Dlya togo shob realizuvati na kupi operaciyi chergi z prioritetami vikoristovuyut she odnu dopomizhnu proceduru Un Max Heapify A i Cya procedura pidtrimuye vlastivist nezrostayuchoyi kupi analogichno Un Min Heapify A i dlya nespadnoyi kupi za umovi yaksho vlastivist kupi porushuyetsya v elementi z indeksom i vin mozhe buti bilshim za batkivskij element Pri comu pripuskayetsya sho v usih inshih elementah vlastivist vikonuyetsya i batkivskij element i go bilshij kozhnogo z nashadkiv i go elementa Procedura pidnimaye element ugoru po derevu doti doki vin ne perestane porushuvati vlastivist kupi Un Max Heapify A i 1 if i 1 2 then return 3 if A Parent i lt A i 4 then Pominyati A Parent i A i displaystyle A Parent i leftrightarrow A i 5 Un Max Heapify A Parent i Chas roboti proceduri ye O logn displaystyle O logn Procedura chergi z prioritetami Insert realizuyetsya takim chinom v kinec kupi dopisuyetsya odin element pri comu rozmir kupi zbilshuyetsya na 1 potim za dopomogoyu Un Max Heapify cej element pidnimayetsya na neobhidnij riven Insert A x 1 heap size A heap size A 1 displaystyle heap size A gets heap size A 1 2 A heap size A x displaystyle A heap size A gets x 3 Un Max Heapify A heap size A Maksimalnij element znahoditsya v pershomu elementi kupi tomu procedura Maximum realizuyetsya trivialno Maximum A 1 if heap size A 0 2 then Pomilka Cherga pusta 3 else return A 1 V proceduri Extract Max rozmir kupi zmenshuyetsya na 1 ostannij element zapisuyetsya na misce pershogo pri comu porushuyetsya vlastivist kupi Vlastivist kupi vidnovlyuyetsya proceduroyu Max Heapify Extract Max A 1 if heap size A 0 2 then Pomilka Cherga pusta 3 max A 1 displaystyle max gets A 1 4 A 1 A heap size A displaystyle A 1 gets A heap size A 5 heap size A heap size A 1 displaystyle heap size A gets heap size A 1 6 if heap size A gt 0 7 then Max Heapify A 1 8 return max U proceduri Change Key mozhlivi tri varianti klyuch elementa zbilshivsya klyuch elementa zmenshivsya klyuch elementa ne zminivsya V zalezhnosti vid variantu vlastivist kupi pislya zmini klyucha treba vidnovlyuvati abo proceduroyu Un Max Heapify abo proceduroyu Max Heapify Change Key A i k 1 old key A i displaystyle old key gets A i 2 A i k displaystyle A i gets k 3 if k gt old key 4 then Un Max Heapify A i 5 elseif k lt old key 6 Max Heapify A i Asimptotichna skladnist operacij Procedura Maximum vikonuyetsya za O 1 displaystyle mathit O 1 proceduri Insert Extract Max Change Key vikonuyutsya za O log2 n displaystyle mathit O log 2 n PrimitkiT Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 Rozdil 6 1 Kupi Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 DzherelaT Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 Rozdil 6 1 Kupi Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 Algoritm sortuvannya kupoyu buv zaproponovanij Vilyamsom 1964 Algorithm 232 Heapsort Communications of the ACM 7 6 347 348 doi 10 1145 512274 512284 Vin takozh opisav sho za dopomogoyu kupi mozhna realizuvati chergu z prioritetom Procedura Build Max Heap bula rozroblena Flojdom Robert W Floyd Algorithm 245 TREESORT Communications of the ACM 7 701 1964 Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi