D-арна купа: відмінності між версіями
Створена сторінка: {{DISPLAYTITLE:''d''-арна купа}} '''<math>d</math>-арна купа''' або '''<math>d</math>-купа''' це структура даних, щ... |
(Немає відмінностей)
|
Версія за 20:41, 1 грудня 2014
-арна купа або -купа це структура даних, що реалізує чергу з пріоритетом, узагальнення бінарної купи в якій вузли мають дочірніх замість 2.[1][2][3] Отже, бінарна купа це 2-купа, а тернарна купа це 3-купа.
Ця структура даних дозволяє операції зменшення пріоритету виконуватись швидше ніж у бінарних купах за рахунок повільнішої операції видалення. Такий компроміс призводить до кращої швидкодії деяких алгоритмів, таких як алгоритм Дейкстри в якому операції зменшення пріоритету відбуваються частіше ніж операції видалення найменшого елемента.[1][4] Додатково, -арні купи краще взаємодіють з кешем процесора порівняно з бінарною купою, що дозволяє їм на практиці виконуватись швидше всупереч теоретично більшому часу виконання у найгіршому випадку.[5][6] Подібно до бінарних куп, -арні купи не потребують додаткової пам'яті окрім пам'яті необхідної для збереження масиву елементів купи.[2][7]
Структура даних
-арна купа складається з масиву з елементів, кожен з яких має пов'язаний з ним пріоритет. Ці елементи можна розглядати як вузли у повному -арному дереві, перелічені у порядку пошуку в ширину: елемент в позиції 0 утворює корінь дерева, елементи в позиціях 1- — його діти, наступні — онуки і т.д. Отже, батьківським елементом для елемента в позиції (для будь-якого ) це елемент в позиції а його дочірні елементи в позиціях з до Згідно з властивістю купи, в мін-купі, кожний елемент має пріоритет не менший ніж пріоритет батьківського елементу; в макс-купа, кожний елемент має пріоритет не більший ніж пріоритет батьківського елементу.[2][3]
Елемент з найменшим пріоритетом в мін-купі (або найбільшим в макс-купі) завжди можна знайти в позиції 0. Для видалення цього елемента, останній елементx в масиві пересувають на його місце і зменшують розмір масива на одиницю. тоді, допоки елемент x і його діти не задовольняють властивості купи, елемент x міняють місцями з одним з його дочірніх (тим, що має найменший пріоритет у мін-купі або тим, що має найбільший пріоритет в макс-купі), пересуваючи його донизу по дереву і в масиві, допоки, зрештою, властивість купи не виконано. Такий самий нисхідний обмін можна використати для збільшення пріоритету елемента в мін-купі або зменшення в макс-купі.[2][3]
Для додавання нового елемента до купи, елемент приєднують у кінець масиву, і міняють місцями з батьківським допоки властивість купи не дотримано. Таку саму висхідну процедуру обмінів можна використати для зменшення пріоритету елемента в мін-купі або збільшення в макс-купі.[2][3]
Для створення нової купи з масиву з елементами, можна обійти елементи у зворотньому порядку, починаючи з останнього і закінчуючи елементом в позиції 0, застосовуючи нисхідний обмін для кожного елемента.[2][3]
 | Ця стаття в процесі редагування певний час. Будь ласка, не редагуйте її, бо Ваші зміни можуть бути втрачені. Якщо ця сторінка не редагувалася кілька днів, будь ласка, приберіть цей шаблон. Це повідомлення призначене для уникнення конфліктів редагування. Останнє редагування зробив користувач Igor Yalovecky (внесок, журнали) о 20:41 UTC (4995599 хвилин тому). |
Примітки
- ↑ а б 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.
- ↑ а б в г д Помилка цитування: Неправильний виклик тегу
<ref>: для виносок під назвоюw07не вказано текст - ↑ Помилка цитування: Неправильний виклик тегу
<ref>: для виносок під назвоюt2не вказано текст - ↑ Помилка цитування: Неправильний виклик тегу
<ref>: для виносок під назвоюnmm91не вказано текст - ↑ Помилка цитування: Неправильний виклик тегу
<ref>: для виносок під назвоюk10не вказано текст - ↑ 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.