-арна купа або -купа це структура даних, що реалізує чергу з пріоритетом, узагальнення бінарної купи в якій вузли мають дочірніх замість 2. Отже, бінарна купа це 2-купа, а тернарна купа це 3-купа.
Ця структура даних дозволяє операції зменшення пріоритету виконуватись швидше ніж у бінарних купах за рахунок повільнішої операції видалення. Такий компроміс приводить до кращої швидкодії деяких алгоритмів, таких як алгоритм Дейкстри, в якому операції зменшення пріоритету відбуваються частіше ніж операції видалення найменшого елемента. Додатково, -арні купи краще взаємодіють з кешем процесора порівняно з бінарною купою, що дозволяє їм на практиці виконуватись швидше всупереч теоретично більшому часу виконання у найгіршому випадку. Подібно до бінарних куп, -арні купи не потребують додаткової пам'яті окрім пам'яті необхідної для збереження масиву елементів купи.
Структура даних
-арна купа складається з масиву з елементів, кожен з яких має пов'язаний з ним пріоритет. Ці елементи можна розглядати як вузли у повному -арному дереві, перелічені у порядку пошуку в ширину: елемент в позиції 0 утворює корінь дерева, елементи в позиціях 1- — його діти, наступні — онуки і т.д. Отже, батьківським елементом для елемента в позиції (для будь-якого ) це елемент в позиції а його дочірні елементи в позиціях з до Згідно з властивістю купи, в мін-купі, кожний елемент має пріоритет не менший ніж пріоритет батьківського елементу; в макс-купа, кожний елемент має пріоритет не більший ніж пріоритет батьківського елементу.
Елемент з найменшим пріоритетом в мін-купі (або найбільшим в макс-купі) завжди можна знайти в позиції 0. Для видалення цього елемента, останній елементx в масиві пересувають на його місце і зменшують розмір масива на одиницю. тоді, допоки елемент x і його діти не задовольняють властивості купи, елемент x міняють місцями з одним з його дочірніх (тим, що має найменший пріоритет у мін-купі або тим, що має найбільший пріоритет в макс-купі), пересуваючи його донизу по дереву і в масиві, допоки, зрештою, властивість купи не виконано. Такий самий спадний обмін можна використати для збільшення пріоритету елемента в мін-купі або зменшення в макс-купі.
Для додавання нового елемента до купи, елемент приєднують у кінець масиву, і міняють місцями з батьківським допоки властивість купи не дотримано. Таку саму висхідну процедуру обмінів можна використати для зменшення пріоритету елемента в мін-купі або збільшення в макс-купі.
Для створення нової купи з масиву з елементами, можна обійти елементи у зворотньому порядку, починаючи з останнього і закінчуючи елементом в позиції 0, застосовуючи спадний обмін для кожного елемента.
Аналіз
У -арній купі з елементами, обидві процедури висхідного і спадного обміну можуть здійснити до обмінів. У разі висхідного обміну, кожен обмін включає одне порівняння елемента з його батьком, і потребує сталого часу. Отже, час щоб вставити елемент до купи, зменшити пріоритет у мін-купі або збільшити в макс-купі є У процедурі спадного обміну, кожен обмін включає порівнянь і потребує часу: необхідно виконати порівнянь, щоб дізнатись максимум або мінімум серед дочірніх елементів і ще одне порівняння для визначення чи потрібен обмін. Звідси, видалення кореня дерева, збільшення пріоритету в мін-купі або зменшення в макс-купі займає
При створенні -арної купи з множини елементів, більшість елементів початково перебувають у позиціях, які зрештою міститимуть листові елементи, і до них спадний обмін не застосовуватиметься. Щонайбільше елементів не є листовими і можуть бути переставлені не більше ніж один раз, за час необхідний на знаходження дочірнього елемента і обмін з ним. Не більше ніж вузлів можуть бути обміняні двічі, потребуючи додатково часу для другого обміну на додачу до першого, який ми вже порахували, і т.д. Тому, у підсумку час для створення купи таким чином є
Точне значення формули (найбільшого можливого числа порівнянь під час створення -арної купи) таке:
- ,
де це сума всіх чисел стандартного представлення числа в -базі і це степінь у факторизації Це зводиться до
- ,
для і до
- ,
для
Використання пам'яті -арною купою з операціями вставки і видалення є лінійним, бо вона не використовує додаткового місця окрім потрібного для розташування масиву, що містить елементи купи. Якщо необхідно підтримувати зміну пріоритету елементів, що перебувають у купі, тоді користувач повинен також зберігати вказівники від елементів до їх позицій у купі, що знов-таки вимагає лінійної пам'яті.
Застосування
Алгоритм Дейкстри для найкоротших шляхів у графах і алгоритм Прима для мінімальних кістякових дерев обидва використовують мін-купу з операціями видалення найменшого елемента і операціями зменшення пріоритету, де це число вершин в графі і це число ребер. Завдяки використанню -арної купи з можна збалансувати підсумковий час цих двох операцій, що призведе до загального часу виконання алгоритму що буде поліпшенням порівняно з у випадку бінарної купи коли кількість ребер значно більша ніж число вершин. Альтернативна структура даних, що втілює чергу з пріоритетом — купа Фібоначчі, дає навіть кращий теоретичний час виконання, але на практиці -арні купи здебільшого щонайменше так само швидкі і часто навіть швидші ніж купи Фібоначчі в поєднанні з цими алгоритмами.
На практиці, 4-купа може показувати кращі результати ніж бінарна купа, навіть для операцій з видалення найменшого елемента. Додатково, -арна купа швидша для розмірів купи, що перевищують розмір кеш пам'яті: Зазвичай, бінарна купа потребує більше і [en] віртуальної пам'яті ніж -арна купа, кожна з яких вимагає набагато більше часу в порівнянні з роботою викликаною додатковими порівняннями, які виконує -арна купа.
Примітки
- Johnson, D. B. (1975), Priority queues with update and finding minimum spanning trees, Information Processing Letters, 4 (3): 53—57, doi:10.1016/0020-0190(75)90001-0.
- Tarjan, R. E. (1983), 3.2. d-heaps, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, т. 44, Society for Industrial and Applied Mathematics, с. 34—38.
- Weiss, M. A. (2007), d-heaps, Data Structures and Algorithm Analysis (вид. 2nd), Addison-Wesley, с. 216, ISBN .
- Tarjan, (1983), pp. 77 and 91.
- Naor, D.; Martel, C. U.; Matloff, N. S. (1991), Performance of priority queue structures in a virtual memory environment, Computer Journal, 34 (5): 428—437, doi:10.1093/comjnl/34.5.428.
- Kamp, Poul-Henning (2010), , ACM Queue, 8 (6), архів оригіналу за 25 грудня 2014, процитовано 2 грудня 2014.
- Mortensen, C. W.; Pettie, S. (2005), The complexity of implicit and space efficient priority queues, Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, Lecture Notes in Computer Science, т. 3608, Springer-Verlag, с. 49—60, doi:10.1007/11534273_6, ISBN .
- Suchenek, Marek A. (2012), , Fundamenta Informaticae, IOS Press, 120 (1): 75—92, doi:10.3233/FI-2012-751, архів оригіналу за 6 жовтня 2014, процитовано 2 грудня 2014.
- Cherkassky, B. V.; Goldberg, A. V.; Radzik, T. (1996), Shortest paths algorithms: Theory and experimental evaluation, Mathematical Programming, 73 (2): 129—174, doi:10.1007/BF02592101.
Посилання
- C++ реалізація узагальненої купи з підтримкою D-купи [ 11 червня 2018 у Wayback Machine.]
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
d displaystyle d arna kupa abo d displaystyle d kupa ce struktura danih sho realizuye chergu z prioritetom uzagalnennya binarnoyi kupi v yakij vuzli mayut d displaystyle d dochirnih zamist 2 Otzhe binarna kupa ce 2 kupa a ternarna kupa ce 3 kupa Cya struktura danih dozvolyaye operaciyi zmenshennya prioritetu vikonuvatis shvidshe nizh u binarnih kupah za rahunok povilnishoyi operaciyi vidalennya Takij kompromis privodit do krashoyi shvidkodiyi deyakih algoritmiv takih yak algoritm Dejkstri v yakomu operaciyi zmenshennya prioritetu vidbuvayutsya chastishe nizh operaciyi vidalennya najmenshogo elementa Dodatkovo d displaystyle d arni kupi krashe vzayemodiyut z keshem procesora porivnyano z binarnoyu kupoyu sho dozvolyaye yim na praktici vikonuvatis shvidshe vsuperech teoretichno bilshomu chasu vikonannya u najgirshomu vipadku Podibno do binarnih kup d displaystyle d arni kupi ne potrebuyut dodatkovoyi pam yati okrim pam yati neobhidnoyi dlya zberezhennya masivu elementiv kupi Struktura danihd displaystyle d arna kupa skladayetsya z masivu z n displaystyle n elementiv kozhen z yakih maye pov yazanij z nim prioritet Ci elementi mozhna rozglyadati yak vuzli u povnomu d displaystyle d arnomu derevi perelicheni u poryadku poshuku v shirinu element v poziciyi 0 utvoryuye korin dereva elementi v poziciyah 1 d displaystyle d jogo diti nastupni d 2 displaystyle d 2 onuki i t d Otzhe batkivskim elementom dlya elementa v poziciyi i displaystyle i dlya bud yakogo i gt 0 displaystyle i gt 0 ce element v poziciyi i 1 d displaystyle lfloor i 1 rfloor d a jogo dochirni elementi v poziciyah z d i 1 displaystyle di 1 do d i d displaystyle di d Zgidno z vlastivistyu kupi v min kupi kozhnij element maye prioritet ne menshij nizh prioritet batkivskogo elementu v maks kupa kozhnij element maye prioritet ne bilshij nizh prioritet batkivskogo elementu Element z najmenshim prioritetom v min kupi abo najbilshim v maks kupi zavzhdi mozhna znajti v poziciyi 0 Dlya vidalennya cogo elementa ostannij elementx v masivi peresuvayut na jogo misce i zmenshuyut rozmir masiva na odinicyu todi dopoki element x i jogo diti ne zadovolnyayut vlastivosti kupi element x minyayut miscyami z odnim z jogo dochirnih tim sho maye najmenshij prioritet u min kupi abo tim sho maye najbilshij prioritet v maks kupi peresuvayuchi jogo donizu po derevu i v masivi dopoki zreshtoyu vlastivist kupi ne vikonano Takij samij spadnij obmin mozhna vikoristati dlya zbilshennya prioritetu elementa v min kupi abo zmenshennya v maks kupi Dlya dodavannya novogo elementa do kupi element priyednuyut u kinec masivu i minyayut miscyami z batkivskim dopoki vlastivist kupi ne dotrimano Taku samu vishidnu proceduru obminiv mozhna vikoristati dlya zmenshennya prioritetu elementa v min kupi abo zbilshennya v maks kupi Dlya stvorennya novoyi kupi z masivu z n displaystyle n elementami mozhna obijti elementi u zvorotnomu poryadku pochinayuchi z ostannogo i zakinchuyuchi elementom v poziciyi 0 zastosovuyuchi spadnij obmin dlya kozhnogo elementa AnalizU d displaystyle d arnij kupi z n displaystyle n elementami obidvi proceduri vishidnogo i spadnogo obminu mozhut zdijsniti do log d n log n log d displaystyle log d n log n log d obminiv U razi vishidnogo obminu kozhen obmin vklyuchaye odne porivnyannya elementa z jogo batkom i potrebuye stalogo chasu Otzhe chas shob vstaviti element do kupi zmenshiti prioritet u min kupi abo zbilshiti v maks kupi ye O log n log d displaystyle O log n log d U proceduri spadnogo obminu kozhen obmin vklyuchaye d displaystyle d porivnyan i potrebuye O d displaystyle O d chasu neobhidno vikonati d 1 displaystyle d 1 porivnyan shob diznatis maksimum abo minimum sered dochirnih elementiv i she odne porivnyannya dlya viznachennya chi potriben obmin Zvidsi vidalennya korenya dereva zbilshennya prioritetu v min kupi abo zmenshennya v maks kupi zajmaye O d log n log d displaystyle O d log n log d Pri stvorenni d displaystyle d arnoyi kupi z mnozhini n displaystyle n elementiv bilshist elementiv pochatkovo perebuvayut u poziciyah yaki zreshtoyu mistitimut listovi elementi i do nih spadnij obmin ne zastosovuvatimetsya Shonajbilshe n d 1 displaystyle n d 1 elementiv ne ye listovimi i mozhut buti perestavleni ne bilshe nizh odin raz za chas O d displaystyle O d neobhidnij na znahodzhennya dochirnogo elementa i obmin z nim Ne bilshe nizh n d 2 1 displaystyle n d 2 1 vuzliv mozhut buti obminyani dvichi potrebuyuchi dodatkovo O d displaystyle O d chasu dlya drugogo obminu na dodachu do pershogo yakij mi vzhe porahuvali i t d Tomu u pidsumku chas dlya stvorennya kupi takim chinom ye i 1 log d n n d i 1 O d O n displaystyle sum i 1 log d n left frac n d i 1 right O d O n Tochne znachennya formuli najbilshogo mozhlivogo chisla porivnyan pid chas stvorennya d displaystyle d arnoyi kupi take d d 1 n s d n d 1 n mod d e d n d 1 displaystyle frac d d 1 n s d n d 1 n mod d e d lfloor frac n d rfloor 1 de s d n displaystyle s d n ce suma vsih chisel standartnogo predstavlennya chisla n displaystyle n v d displaystyle d bazi i e d n displaystyle e d n ce stepin d displaystyle d u faktorizaciyi n displaystyle n Ce zvoditsya do 2 n 2 s 2 n e 2 n displaystyle 2n 2s 2 n e 2 n dlya d 2 displaystyle d 2 i do 3 2 n s 3 n 2 e 3 n e 3 n 1 displaystyle frac 3 2 n s 3 n 2e 3 n e 3 n 1 dlya d 3 displaystyle d 3 Vikoristannya pam yati d displaystyle d arnoyu kupoyu z operaciyami vstavki i vidalennya ye linijnim bo vona ne vikoristovuye dodatkovogo miscya okrim potribnogo dlya roztashuvannya masivu sho mistit elementi kupi Yaksho neobhidno pidtrimuvati zminu prioritetu elementiv sho perebuvayut u kupi todi koristuvach povinen takozh zberigati vkazivniki vid elementiv do yih pozicij u kupi sho znov taki vimagaye linijnoyi pam yati ZastosuvannyaAlgoritm Dejkstri dlya najkorotshih shlyahiv u grafah i algoritm Prima dlya minimalnih kistyakovih derev obidva vikoristovuyut min kupu z n displaystyle n operaciyami vidalennya najmenshogo elementa i m displaystyle m operaciyami zmenshennya prioritetu de n displaystyle n ce chislo vershin v grafi i m displaystyle m ce chislo reber Zavdyaki vikoristannyu d displaystyle d arnoyi kupi z d m n displaystyle d m n mozhna zbalansuvati pidsumkovij chas cih dvoh operacij sho prizvede do zagalnogo chasu vikonannya algoritmu O m log m n n displaystyle O m log m n n sho bude polipshennyam porivnyano z O m log n displaystyle O m log n u vipadku binarnoyi kupi koli kilkist reber znachno bilsha nizh chislo vershin Alternativna struktura danih sho vtilyuye chergu z prioritetom kupa Fibonachchi daye navit krashij teoretichnij chas vikonannya O m n log n displaystyle O m n log n ale na praktici d displaystyle d arni kupi zdebilshogo shonajmenshe tak samo shvidki i chasto navit shvidshi nizh kupi Fibonachchi v poyednanni z cimi algoritmami Na praktici 4 kupa mozhe pokazuvati krashi rezultati nizh binarna kupa navit dlya operacij z vidalennya najmenshogo elementa Dodatkovo d displaystyle d arna kupa shvidsha dlya rozmiriv kupi sho perevishuyut rozmir kesh pam yati Zazvichaj binarna kupa potrebuye bilshe i en virtualnoyi pam yati nizh d displaystyle d arna kupa kozhna z yakih vimagaye nabagato bilshe chasu v porivnyanni z robotoyu viklikanoyu dodatkovimi porivnyannyami yaki vikonuye d displaystyle d arna kupa PrimitkiJohnson D B 1975 Priority queues with update and finding minimum spanning trees Information Processing Letters 4 3 53 57 doi 10 1016 0020 0190 75 90001 0 Tarjan R E 1983 3 2 d heaps Data Structures and Network Algorithms CBMS NSF Regional Conference Series in Applied Mathematics t 44 Society for Industrial and Applied Mathematics s 34 38 Weiss M A 2007 d heaps Data Structures and Algorithm Analysis vid 2nd Addison Wesley s 216 ISBN 0 321 37013 9 Tarjan 1983 pp 77 and 91 Naor D Martel C U Matloff N S 1991 Performance of priority queue structures in a virtual memory environment Computer Journal 34 5 428 437 doi 10 1093 comjnl 34 5 428 Kamp Poul Henning 2010 ACM Queue 8 6 arhiv originalu za 25 grudnya 2014 procitovano 2 grudnya 2014 Mortensen C W Pettie S 2005 The complexity of implicit and space efficient priority queues Algorithms and Data Structures 9th International Workshop WADS 2005 Waterloo Canada August 15 17 2005 Proceedings Lecture Notes in Computer Science t 3608 Springer Verlag s 49 60 doi 10 1007 11534273 6 ISBN 978 3 540 28101 6 Suchenek Marek A 2012 Fundamenta Informaticae IOS Press 120 1 75 92 doi 10 3233 FI 2012 751 arhiv originalu za 6 zhovtnya 2014 procitovano 2 grudnya 2014 Cherkassky B V Goldberg A V Radzik T 1996 Shortest paths algorithms Theory and experimental evaluation Mathematical Programming 73 2 129 174 doi 10 1007 BF02592101 PosilannyaC realizaciya uzagalnenoyi kupi z pidtrimkoyu D kupi 11 chervnya 2018 u Wayback Machine