d-арна купа

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

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

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

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

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

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

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

Аналіз

У $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).$

При створенні $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).$

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

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

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

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

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

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

для $d=3.$

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

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

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

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

Посилання

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