D-арна купа

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

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

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

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

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

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

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

Аналіз

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

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

${\displaystyle \sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).}$^[2][3]

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

${\displaystyle {\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n\mod d))(e_{d}(\lfloor {\frac {n}{d}}\rfloor )+1)}$,^[8]

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

${\displaystyle 2n-2s_{2}(n)-e_{2}(n)}$, ^[8]

для ${\displaystyle d=2,}$ і до

${\displaystyle {\frac {3}{2}}(n-s_{3}(n))-2e_{3}(n)-e_{3}(n-1)}$,^[8]

для ${\displaystyle d=3.}$

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

Застосування

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

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

Примітки

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.
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.
3. Weiss, M. A. (2007), d-heaps, Data Structures and Algorithm Analysis (вид. 2nd), Addison-Wesley, с. 216, ISBN 0-321-37013-9.
4. Tarjan, (1983), pp. 77 and 91.
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.
6. Kamp, Poul-Henning (2010), You're doing it wrong, ACM Queue, 8 (6), архів оригіналу за 25 грудня 2014, процитовано 2 грудня 2014.
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.
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.

Посилання

• C++ реалізація узагальненої купи з підтримкою D-купи [Архівовано 11 червня 2018 у Wayback Machine.]