d-арна купа

${\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}$-арна купа швидша для розмірів купи, що перевищують розмір кеш пам'яті: Зазвичай, бінарна купа потребує більше хиб кешу і помилок сторінок віртуальної пам'яті ніж ${\displaystyle d}$-арна купа, кожна з яких вимагає набагато більше часу в порівнянні з роботою викликаною додатковими порівняннями, які виконує ${\displaystyle d}$-арна купа.[5][6]

• C++ реалізація узагальненої купи з підтримкою D-купи