d-арна купа

$d$ -арна купа або $d$ -купа це структура даних, що реалізує чергу з пріоритетом, узагальнення бінарної купи в якій вузли мають $d$ дочірніх замість 2.^[1]^[2]^[3] Отже, бінарна купа це 2-купа, а тернарна купа це 3-купа.

Ця структура даних дозволяє операції зменшення пріоритету виконуватись швидше ніж у бінарних купах за рахунок повільнішої операції видалення. Такий компроміс приводить до кращої швидкодії деяких алгоритмів, таких як алгоритм Дейкстри, в якому операції зменшення пріоритету відбуваються частіше ніж операції видалення найменшого елемента.^[1]^[4] Додатково, $d$ -арні купи краще взаємодіють з кешем процесора порівняно з бінарною купою, що дозволяє їм на практиці виконуватись швидше всупереч теоретично більшому часу виконання у найгіршому випадку.^[5]^[6] Подібно до бінарних куп, $d$ -арні купи не потребують додаткової пам'яті окрім пам'яті необхідної для збереження масиву елементів купи.^[2]^[7]

Структура даних ред.

$d$ -арна купа складається з масиву з $n$ елементів, кожен з яких має пов'язаний з ним пріоритет. Ці елементи можна розглядати як вузли у повному $d$ -арному дереві, перелічені у порядку пошуку в ширину: елемент в позиції 0 утворює корінь дерева, елементи в позиціях 1- $d$ — його діти, наступні $d^{2}$ — онуки і т.д. Отже, батьківським елементом для елемента в позиції $i$ (для будь-якого $i>0$ ) це елемент в позиції $\lfloor i-1\rfloor /d,$ а його дочірні елементи в позиціях з $di+1$ до $di+d.$ Згідно з властивістю купи, в мін-купі, кожний елемент має пріоритет не менший ніж пріоритет батьківського елементу; в макс-купа, кожний елемент має пріоритет не більший ніж пріоритет батьківського елементу.^[2]^[3]

Елемент з найменшим пріоритетом в мін-купі (або найбільшим в макс-купі) завжди можна знайти в позиції 0. Для видалення цього елемента, останній елементx в масиві пересувають на його місце і зменшують розмір масива на одиницю. тоді, допоки елемент x і його діти не задовольняють властивості купи, елемент x міняють місцями з одним з його дочірніх (тим, що має найменший пріоритет у мін-купі або тим, що має найбільший пріоритет в макс-купі), пересуваючи його донизу по дереву і в масиві, допоки, зрештою, властивість купи не виконано. Такий самий спадний обмін можна використати для збільшення пріоритету елемента в мін-купі або зменшення в макс-купі.^[2]^[3]

Для додавання нового елемента до купи, елемент приєднують у кінець масиву, і міняють місцями з батьківським допоки властивість купи не дотримано. Таку саму висхідну процедуру обмінів можна використати для зменшення пріоритету елемента в мін-купі або збільшення в макс-купі.^[2]^[3]

Для створення нової купи з масиву з $n$ елементами, можна обійти елементи у зворотньому порядку, починаючи з останнього і закінчуючи елементом в позиції 0, застосовуючи спадний обмін для кожного елемента.^[2]^[3]

Аналіз ред.

У $d$ -арній купі з $n$ елементами, обидві процедури висхідного і спадного обміну можуть здійснити до $\log _{d}n=\log n/\log d$ обмінів. У разі висхідного обміну, кожен обмін включає одне порівняння елемента з його батьком, і потребує сталого часу. Отже, час щоб вставити елемент до купи, зменшити пріоритет у мін-купі або збільшити в макс-купі є $O(\log n/\log d).$ У процедурі спадного обміну, кожен обмін включає $d$ порівнянь і потребує $O(d)$ часу: необхідно виконати $d-1$ порівнянь, щоб дізнатись максимум або мінімум серед дочірніх елементів і ще одне порівняння для визначення чи потрібен обмін. Звідси, видалення кореня дерева, збільшення пріоритету в мін-купі або зменшення в макс-купі займає $O(d\log n/\log d).$ ^[2]^[3]

При створенні $d$ -арної купи з множини $n$ елементів, більшість елементів початково перебувають у позиціях, які зрештою міститимуть листові елементи, і до них спадний обмін не застосовуватиметься. Щонайбільше $n/d+1$ елементів не є листовими і можуть бути переставлені не більше ніж один раз, за час $O(d)$ необхідний на знаходження дочірнього елемента і обмін з ним. Не більше ніж $n/d^{2}+1$ вузлів можуть бути обміняні двічі, потребуючи додатково $O(d)$ часу для другого обміну на додачу до першого, який ми вже порахували, і т.д. Тому, у підсумку час для створення купи таким чином є

\sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).

^[2]^[3]

Точне значення формули (найбільшого можливого числа порівнянь під час створення $d$ -арної купи) таке:

{\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n\mod d))(e_{d}(\lfloor {\frac {n}{d}}\rfloor )+1)

,^[8]

де $s_{d}(n)$ це сума всіх чисел стандартного представлення числа $n$ в $d$ -базі і $e_{d}(n)$ це степінь $d$ у факторизації $n.$ Це зводиться до

2n-2s_{2}(n)-e_{2}(n)

, ^[8]

для $d=2,$ і до

{\frac {3}{2}}(n-s_{3}(n))-2e_{3}(n)-e_{3}(n-1)

,^[8]

для $d=3.$

Використання пам'яті $d$ -арною купою з операціями вставки і видалення є лінійним, бо вона не використовує додаткового місця окрім потрібного для розташування масиву, що містить елементи купи.^[2]^[7] Якщо необхідно підтримувати зміну пріоритету елементів, що перебувають у купі, тоді користувач повинен також зберігати вказівники від елементів до їх позицій у купі, що знов-таки вимагає лінійної пам'яті.^[2]

Застосування ред.

Алгоритм Дейкстри для найкоротших шляхів у графах і алгоритм Прима для мінімальних кістякових дерев обидва використовують мін-купу з $n$ операціями видалення найменшого елемента і $m$ операціями зменшення пріоритету, де $n$ це число вершин в графі і $m$ це число ребер. Завдяки використанню $d$ -арної купи з $d=m/n,$ можна збалансувати підсумковий час цих двох операцій, що призведе до загального часу виконання алгоритму $O(m\log _{m/n}n),$ що буде поліпшенням порівняно з $O(m\log n)$ у випадку бінарної купи коли кількість ребер значно більша ніж число вершин.^[1]^[4] Альтернативна структура даних, що втілює чергу з пріоритетом — купа Фібоначчі, дає навіть кращий теоретичний час виконання, $O(m+n\log n),$ але на практиці $d$ -арні купи здебільшого щонайменше так само швидкі і часто навіть швидші ніж купи Фібоначчі в поєднанні з цими алгоритмами.^[9]

На практиці, 4-купа може показувати кращі результати ніж бінарна купа, навіть для операцій з видалення найменшого елемента.^[2]^[3] Додатково, $d$ -арна купа швидша для розмірів купи, що перевищують розмір кеш пам'яті: Зазвичай, бінарна купа потребує більше хиб кешу і помилок сторінок^[en] віртуальної пам'яті ніж $d$ -арна купа, кожна з яких вимагає набагато більше часу в порівнянні з роботою викликаною додатковими порівняннями, які виконує $d$ -арна купа.^[5]^[6]

Примітки ред.

↑ ^а ^б ^в 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 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), You're doing it wrong, 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 978-3-540-28101-6.
↑ ^а ^б ^в Suchenek, Marek A. (2012), Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program, 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.]

[j75-1] а ^б ^в 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.

[t83-2] а ^б ^в ^г ^д ^е ^ж ^и ^к ^л ^м 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.

[w07-3] а ^б ^в ^г ^д ^е ^ж ^и Weiss, M. A. (2007), d-heaps, Data Structures and Algorithm Analysis (вид. 2nd), Addison-Wesley, с. 216, ISBN 0-321-37013-9.

[t2-4] а ^б Tarjan, (1983), pp. 77 and 91.

[nmm91-5] а ^б 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.

[k10-6] а ^б Kamp, Poul-Henning (2010), You're doing it wrong, ACM Queue, 8 (6), архів оригіналу за 25 грудня 2014, процитовано 2 грудня 2014.

[mp05-7] а ^б 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 978-3-540-28101-6.

[Suchenek-8] а ^б ^в Suchenek, Marek A. (2012), Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program, Fundamenta Informaticae, IOS Press, 120 (1): 75—92, doi:10.3233/FI-2012-751, архів оригіналу за 6 жовтня 2014, процитовано 2 грудня 2014.

[9] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]