Черга на основі відер

Массив відер, придатних для пріоритетів у діапазоні від 1 до 6. Елемент із мінімальним пріоритетом можна знайти в крайньому лівому непорожньому відрі.
Тип	Черга з пріоритетом
Винахідник	Роберт Діал
Рік винаходу	1969
Середня вставка	O(1)
Найгірша вставка	O(1)
Середнє видалення мінімуму	O(#пріоритетів)
Найгірше видалення мінімуму	O(#пріоритетів)
Середнє знаходження мінімуму	O(#пріоритетів)
Найгірше знаходження мінімуму	O(#пріоритетів)
Середнє зменшення ключа	O(1)
Найгірше зменшення ключа	O(1)

Черга на основі відер — це структура даних, яка реалізує пріоритетну чергу: вона підтримує динамічну колекцію елементів з числовими пріоритетами і забезпечує швидкий доступ до елемента з мінімальним (або максимальним) пріоритетом. У черзі на основі відер пріоритети мають бути цілими числами, і вона особливо підходить для застосувань, у яких пріоритети мають невеликий діапазон.[1] Черга на основі відер має форму масиву відер: масив, індексований за пріоритетами, осередки якого містять колекції елементів з однаковим пріоритетом. Завдяки цій структурі даних вставка елементів і зміни їхнього пріоритету виконуються за сталий час. Пошук і видалення елемента з мінімальним пріоритетом займає час, пропорційний кількості відер, або, за допомогою збереження вказівника на щойно знайдене відро, час, пропорційний різниці пріоритетів між послідовними операціями.

Черга на основі відер є аналогом пріоритетної черги для Сортування Діріхле (також відомого як сортування за відрами), алгоритму сортування, що розміщує елементи у відра, індексовані за пріоритетами, а потім об'єднує ці відра. Використання черги на основі відер як пріоритетної черги у сортування вибором призводить до варіації алгоритму сортування за відрами.[2] Черги на основі відер також називають чергами пріоритетів на основі відер[3] або чергами пріоритетів із обмеженою висотою.[1] Якщо їх використовують для квантованих наближень до дійсних чисел у якості пріоритетів, їх також називають неупорядкованими чергами пріоритетів[4] або псевдо чергами пріоритетів.[5] Вони тісно пов'язані з календарною чергою, структурою, яка використовує подібний масив відер для точного пріоритизації за дійсними числами.

Застосування черги на основі відер включає обчислення дегенерації графа, швидкі алгоритми для найкоротших шляхів та найширших шляхів для графів з вагами, що є малими цілими числами або вже впорядковані, а також жадібні апроксимаційні алгоритми для задачі покриття множини. Квантована версія цієї структури також застосовувалася для планування[2] та для marching cubes у комп'ютерній графіці.[4] Перше використання черги на основі відер[6] було в алгоритмі пошуку найкоротшого шляху, запропонованому Dial, (1969).[7]

Операція

Основна структура даних

Черга на основі відер може обробляти елементи з цілими пріоритетами в діапазоні від 0 або 1 до відомої межі C та виконувати операції вставки елементів, зміни пріоритету елементів або витягання (пошук та видалення) елемента з мінімальним (або максимальним) пріоритетом. Вона складається з масиву A структур даних-контейнерів; у більшості джерел ці контейнери є двонаправленими списками, але вони можуть бути також динамічними масивами[3] або динамічними множинами. Контейнер у p-тій комірці масиву A[p] зберігає колекцію елементів, чий пріоритет дорівнює p.

Черга на основі відер може виконувати наступні операції:

• Щоб вставити елемент x з пріоритетом p, додайте x до контейнера в A[p].
• Щоб змінити пріоритет елемента, видаліть його з контейнера старого пріоритету і повторно вставте його в контейнер нового пріоритету.
• Щоб витягти елемент з мінімальним або максимальним пріоритетом, виконайте лінійний пошук в масиві, щоб знайти перший або останній непорожній контейнер відповідно, виберіть довільний елемент з цього контейнера і видаліть його з контейнера.

Таким чином, вставка та зміна пріоритетів займають постійний час, а витягування елемента з мінімальним або максимальним пріоритетом займає час O(C).[1][6][8]

Оптимізації

Як оптимізацію, структура даних може починати кожний послідовний пошук непорожнього відра з останнього знайденого непорожнього відра замість початку масиву. Це можна зробити одним з двох способів: лінивим (затримуючи ці послідовні пошуки до їхньої необхідності) або завчасним (здійснюючи пошуки заздалегідь). Вибір часу для виконання пошуку впливає на те, яка з операцій структури даних сповільнюється цими пошуками. Оригінальна версія структури Дайла використовувала лінивий пошук. Це можна реалізувати, підтримуючи індекс L, який є нижня межа мінімального пріоритету будь-якого елемента, що зараз знаходиться в черзі. При вставці нового елемента L слід оновити до мінімального з його старого значення і нового пріоритету елемента. При пошуку елемента з мінімальним пріоритетом пошук можна почати з L замість з нуля, і після пошуку L слід залишити рівним пріоритету, знайденому під час пошуку.[7][9] Альтернативно, завчасна версія цієї оптимізації підтримує L оновленим так, щоб він завжди вказував на перше непорожнє відро. При вставці нового елемента з пріоритетом меншим ніж L, структура даних встановлює L на новий пріоритет, а при видаленні останнього елемента з відра з пріоритетом L, виконується послідовний пошук через більші індекси до знаходження непорожнього відра і встановлення L на пріоритет отриманого відра.[1]

В обох цих варіаціях кожний послідовний пошук займає час, пропорційний різниці між старим і новим значенням L. Це може бути значно швидше, ніж межа часу O(C) для пошуків у не оптимізованій версії структури даних. У багатьох застосуваннях пріоритетних черг, таких як алгоритм Дейкстри, мінімальні пріоритети формують монотонна послідовність, що дозволяє використовувати монотонну пріоритетну чергу. У цих застосуваннях, як для лінивих, так і для завчасних варіацій оптимізованої структури, послідовні пошуки непорожніх відер охоплюють неперетинні діапазони відер. Оскільки кожне відро входить максимум до одного з цих діапазонів, кількість їх кроків разом не перевищує C. Тому, у цих застосуваннях, загальний час для послідовності з n операцій становить O(n + C), а не повільніша межа часу O(nC) яка б виникла без цієї оптимізації.[9] Відповідну оптимізацію можна застосувати в додатках, де черга з відрами використовується для знаходження елементів з максимальним пріоритетом, але в цьому випадку слід підтримувати індекс, який встановлює верхню межу для максимального пріоритету, а послідовний пошук непорожнього відра слід проводити вниз від цієї верхньої межі.[10] Ще одна оптимізація (запропонована Dial, 1969) може бути використана для економії простору, коли пріоритети є монотонними і, протягом алгоритму, завжди потрапляють у діапазон r значень, а не розтягуються на весь діапазон від 0 до C. У цьому випадку можна індексувати масив за пріоритетами по модулю r, а не за їхніми фактичними значеннями. Пошук елемента з мінімальним пріоритетом слід завжди починати з попереднього мінімуму, щоб уникнути пріоритетів, які вищі за мінімум, але мають менші модулі. Зокрема, ця ідея може бути застосована в алгоритмі Дейкстри для графів, у яких довжини ребер є цілими числами в діапазоні від 1 до r.[8]

Оскільки створення нової черги з відрами передбачає ініціалізацію масиву порожніх відер, цей крок ініціалізації займає час, пропорційний кількості пріоритетів. Варіація черги з відрами, описана Donald B. Johnson(інші мови) у 1981 році, натомість зберігає тільки непорожні відра у зв'язаному списку, відсортованому за їхніми пріоритетами, і використовує допоміжне дерево пошуку для швидкого знаходження позиції в цьому зв'язаному списку для будь-яких нових відер. Ініціалізація цієї варіантної структури займає час O(log log C), знаходження елемента з мінімальним або максимальним пріоритетом займає константний час, а вставка або видалення елемента займає час O(log log D), де D — різниця між найближчими меншими та більшими пріоритетами до пріоритету вставленого або видаленого елемента.[11]

Приклад

Наприклад, розглянемо чергу з відрами з чотирма пріоритетами: числа 0, 1, 2 та 3. Вона складається з масиву ${\displaystyle A}$, чотири комірки якого містять колекцію елементів, спочатку порожніх. Для цілей цього прикладу, ${\displaystyle A}$ можна записати як список з чотирьох наборів: ${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\emptyset ]}$. Розглянемо послідовність операцій, в якій ми вставляємо два елементи ${\displaystyle x}$ та ${\displaystyle y}$ з однаковим пріоритетом 1, вставляємо третій елемент ${\displaystyle z}$ з пріоритетом 3, змінюємо пріоритет ${\displaystyle x}$ на 3 і потім виконуємо дві витягання елемента з мінімальним пріоритетом.

• Після вставлення ${\displaystyle x}$ з пріоритетом 1, ${\displaystyle A=[\emptyset ,\{x\},\emptyset ,\emptyset ]}$.
• Після вставлення ${\displaystyle y}$ з пріоритетом 1, ${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\emptyset ]}$.
• Після вставлення ${\displaystyle z}$ з пріоритетом 3, ${\displaystyle A=[\emptyset ,\{x,y\},\emptyset ,\{z\}]}$.
• Зміна пріоритету ${\displaystyle x}$ з 1 на 3 передбачає видалення його з ${\displaystyle A[1]}$ та додавання до ${\displaystyle A[3]}$, після чого ${\displaystyle A=[\emptyset ,\{y\},\emptyset ,\{x,z\}]}$.
• Витягування елемента з мінімальним пріоритетом у базовій версії черги з відрами здійснюється шляхом пошуку з початку ${\displaystyle A}$, щоб знайти перший непорожній елемент: ${\displaystyle A[0]}$ порожній, але ${\displaystyle A[1]=\{y\}}$, непорожній набір. Вибирається довільний елемент цього набору (єдиний елемент, ${\displaystyle y}$) як елемент з мінімальним пріоритетом. Видалення ${\displaystyle y}$ з структури залишає ${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x,z\}]}$.
• Друге витягування в базовій версії черги з відрами знову здійснюється шляхом пошуку з початку масиву: ${\displaystyle A[0]=\emptyset }$, ${\displaystyle A[1]=\emptyset }$, ${\displaystyle A[2]=\emptyset }$, ${\displaystyle A[3]=\{x,z\}}$, непорожній. В удосконалених варіантах черги з відрами цей пошук починається з останньої позиції, яка була знайдена як непорожня, ${\displaystyle A[1]}$. У будь-якому випадку ${\displaystyle A[3]=\{x,z\}}$ виявляється першим непорожнім набором. Один з його елементів вибирається довільно як елемент з мінімальним пріоритетом; наприклад, може бути вибраний ${\displaystyle z}$. Цей елемент видаляється, залишаючи ${\displaystyle A=[\emptyset ,\emptyset ,\emptyset ,\{x\}]}$.

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

Дегерація графа

Через чергу відер можна підтримувати вершини ненаправленого графа, пріоритетизуючи їх за ступенем, і повторно знаходити та видаляти вершину з мінімальним ступенем.[1] Цей жадібний алгоритм можна використовувати для обчислення дегерації даного графа, яка дорівнює найбільшому ступеню будь-якої вершини на момент її видалення. Алгоритм виконується за лінійний час, з оптимізацією або без неї, яка підтримує нижню межу на мінімальний пріоритет, оскільки кожна вершина знаходиться за час, пропорційний її ступеню, і сума всіх ступенів вершин є лінійною відносно кількості ребер графа.[12]

Алгоритм Дайла для найкоротших шляхів

У алгоритмі Дейкстри для найкоротший шляхів у орієнтований графах з вагами ребер, що є додатними цілими числами, пріоритети є монотонними,[13] і монотонну чергу відер можна використовувати для досягнення часових меж O(m + dc), де m — кількість ребер, d — діаметр мережі, а c — максимальна (ціла) вартість зв'язку.[9][14] Цей варіант алгоритму Дейкстри також відомий як алгоритм Дайла,[9] на честь Роберта Б. Дайла, який опублікував його в 1969 році.[7] Та сама ідея також працює, використовуючи квантовану чергу відер, для графів з додатніми дійсними вагами ребер, коли співвідношення максимального до мінімального ваги не перевищує c.[15] У цій квантованій версії алгоритму вершини обробляються не в порядку, порівняно з результатом, отриманим з не квантованою чергою пріоритетів, але правильні найкоротші шляхи все ще знаходяться.[5] У цих алгоритмах пріоритети будуть охоплювати лише діапазон шириною c + 1, тому модульна оптимізація може бути використана для зменшення простору до O(n + c).[8][14]

Варіант того ж алгоритму можна використовувати для проблема найширшого шляху. У поєднанні з методами швидкого розподілу нецілих ваг ребер на підмножини, які можна присвоїти цілі пріоритети, це призводить до майже лінійних рішень для версії найширшого шляху з одного джерела до однієї мети.[16]

Жадібне покриття множин

Проблема покриття множин має на вході сімейство множин. Виходом повинна бути підмножина цих множин з такою ж об'єднанням, як у вихідної сім'ї, що містить якомога менше множин. Це NP-складна проблема, але має жадібний наближувальний алгоритм, який досягає логарифмічної апроксимації, що є в основному найкращим можливим варіантом, якщо P ≠ NP.[17] Цей наближувальний алгоритм вибирає свою підмножину, постійно обираючи множину, яка покриває максимальну кількість залишкових непокритих елементів.[18] Стандартне завдання з проектування алгоритмів вимагає реалізації цього алгоритму, яка займає лінійний час від розміру входу, що є сумою розмірів усіх вхідних множин.[19]

Цю задачу можна вирішити за допомогою черги відер множин у вхідній сім'ї, пріоритетизованих за кількістю залишкових елементів, які вони покривають. Щоразу, коли жадібний алгоритм вибирає множину як частину свого виходу, нові покриті елементи множини повинні бути відняті з пріоритетів інших множин, що їх покривають; протягом алгоритму кількість цих змін пріоритетів дорівнює просто сумі розмірів вхідних множин. Пріоритети є монотонно зменшувальними цілими числами, верхня межа яких визначається кількістю елементів, які потрібно покрити. Кожен вибір жадібного алгоритму включає знаходження множини з максимальним пріоритетом, що можна зробити, скануючи вниз через відра черги відер, починаючи з найостаннішого попереднього максимального значення. Загальний час є лінійним від розміру входу.[10] Див. зокрема Розділ 2.4, «Черга пріоритетів», с. 22.

Планування

Черги відер можна використовувати для планування завдань з термінами виконання, наприклад, в пакетна передача для інтернет-даних з гарантіями якість обслуговування. Для цього застосування терміни виконання повинні бути квантизовані в дискретні інтервали, і завдання, терміни виконання яких потрапляють в один і той же інтервал, вважаються такими, що мають однаковий пріоритет.[2]

Варіація квантизованої структури даних черги відер, календарна черга, була застосована для планування дискретно-подійних симуляцій, де елементи в черзі є майбутніми подіями, пріоритетизованими за часом у симуляції, коли події повинні відбутися. У цьому застосуванні порядок подій є критичним, тому пріоритети не можуть бути апроксимовані. Тому календарна черга виконує пошуки елемента з мінімальним пріоритетом інакше ніж черга відер: у черзі відер будь-який елемент першого непорожнього відра може бути повернутий, але календарна черга замість цього шукає всі елементи в цьому відрі, щоб визначити, який з них має найменший не квантизований пріоритет. Щоб ці пошуки залишалися швидкими, ця варіація намагається підтримувати кількість відер пропорційною кількості елементів, шляхом коригування масштабу квантизації та перебудови структури даних, коли вона виходить з балансу. Календарні черги можуть бути повільнішими за черги відер у найгіршому випадку (коли багато елементів потрапляють в одне й те саме найменше відро), але є швидкими, коли елементи рівномірно розподілені між відрами, що призводить до постійного середнього розміру відра.[20][21]

Швидке марширування

В прикладна математика і числові методи для розв'язання диференціальні рівняння використовуються нечіткі черги пріоритетів для пріоритетизації кроків метод швидкого марширування для розв'язання крайова задача рівняння Ейконала, яке використовується для моделювання розповсюдження хвиль. Цей метод знаходить часи, в які рухома межа перетинає набір дискретних точок (наприклад, точки цілочислової сітки), використовуючи метод пріоритетизації, що нагадує безперервну версію алгоритму Дейкстра, і його час виконання визначається чергою пріоритетів цих точок. Його можна прискорити до лінійного часу, округлюючи пріоритети, що використовуються в цьому алгоритмі, до цілих чисел і використовуючи чергу відер для цих цілих чисел. Як і в алгоритмах Дейкстри та Дайла, пріоритети є монотонними, тому метод швидкого марширування може використовувати монотонну оптимізацію черги відер та її аналіз. Однак квантизація вводить деяку помилку в результуючі обчислення.[4]

Див. також

• Soft heap(інші мови), інший спосіб прискорення черг пріоритетів шляхом використання апроксимованих пріоритетів

Примітки

1. Скієна, Стівен С. (1998), Посібник з проектування алгоритмів, Springer, с. 181, ISBN 9780387948607.
2. Figueira, N. R. (1997), Рішення задачі черги пріоритетів для дисциплін обслуговування за термінами, Матеріали шостої міжнародної конференції з комп'ютерних комунікацій і мереж, IEEE Computer Society Press, с. 320—325, doi:10.1109/icccn.1997.623330, S2CID 5611516
3. Хенцінгер, Моніка; Ное, Александер; Шульц, Крістіан (2019). Розподілені мінімальні точні розрізи в спільній пам'яті. 2019 IEEE Міжнародний симпозіум з розподіленої та паралельної обробки, IPDPS 2019, Ріо-де-Жанейро, Бразилія, 20-24 травня 2019. с. 13—22. arXiv:1808.05458. doi:10.1109/IPDPS.2019.00013. S2CID 52019258.
4. Rasch, Christian; Satzger, Thomas (2009). Remarks on the O(N) implementation of the fast marching method (PDF). IMA Journal of Numerical Analysis. Т. 29, № 3. с. 806—813. doi:10.1093/imanum/drm028. MR 2520171.
5. Robledo, Alicia; Guivant, José E. (2010), Pseudo priority queues for real-time performance on dynamic programming processes applied to path planning (PDF), у Wyeth, Gordon; Upcroft, Ben (ред.), Australasian Conference on Robotics and Automation
6. Edelkamp, Stefan; Schroedl, Stefan (2011). 3.1.1 Структури даних на основі відер. Heuristic Search: Theory and Applications. Elsevier. с. 90—92. ISBN 9780080919737.. Див. також с. 157 для історії та назви цієї структури.
7. Dial, Robert B. (1969). Algorithm 360: Shortest-path forest with topological ordering [H]. Communications of the ACM. 12 (11): 632—633. doi:10.1145/363269.363610. S2CID 6754003..
8. Мехльгорн, Курт; Сандерс, Пітер (2008), 10.5.1 Черги на основі відер, Алгоритми та структури даних: Основний набір інструментів, Springer, с. 201, ISBN 9783540779773.
9. Bertsekas, Dimitri P. (1991), Dial's algorithm, Linear Network Optimization: Algorithms And Codes, Cambridge, Massachusetts: MIT Press, с. 72—75, ISBN 0-262-02334-2, MR 1201582
10. Lim, C. L.; Moffat, Alistair; Wirth, Anthony Ian (2014), Ліниві та жадібні підходи до задачі покриття множин, у Thomas, Bruce; Parry, Dave (ред.), Тридцять сьома Австралійська конференція з комп'ютерних наук, ACSC 2014, Окленд, Нова Зеландія, січень 2014 року, CRPIT, т. 147, Австралійське комп'ютерне товариство, с. 19—27
11. Johnson, Donald B. (1981), Черга з пріоритетами, в якій ініціалізація та операції черги займають час O(log log D), Mathematical Systems Theory, 15 (4): 295—309, doi:10.1007/BF01786986, MR 0683047, S2CID 35703411
12. Matula, David W.; Beck, L. L. (1983), Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM, 30 (3): 417—427, doi:10.1145/2402.322385, MR 0709826, S2CID 4417741.
13. Varghese, George (2005), Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices, Morgan Kaufmann, с. 78—80, ISBN 9780120884773.
14. Festa, Paola (2006), Shortest path algorithms, у Resende, Mauricio G. C.; Pardalos, Panos M. (ред.), Handbook of Optimization in Telecommunications, Boston: Springer, с. 185—210, doi:10.1007/978-0-387-30165-5_8; див. зокрема розділ 8.3.3.6, «Реалізація Дайла», с. 194—195.
15. Mehlhorn та Sanders, (2008) (Завдання 10.11, с. 201) приписують цю ідею статті 1978 року Е. А. Диница (Єфим Динітц).
16. Gabow, Harold N.; Tarjan, Robert E. (1988), Algorithms for two bottleneck optimization problems, Journal of Algorithms, 9 (3): 411—417, doi:10.1016/0196-6774(88)90031-4, MR 0955149
17. Dinur, Irit; Steurer, David (2014), Аналіз підходу до паралельного повторення, у Shmoys, David B. (ред.), Симпозіум з теорії обчислень, STOC 2014, Нью-Йорк, США, 31 травня - 3 червня 2014 року, ACM, с. 624—633, arXiv:1305.1979, doi:10.1145/2591796.2591884, MR 3238990, S2CID 15252482
18. Johnson, David S. (1974), Наближувальні алгоритми для комбінаторних проблем, Journal of Computer and System Sciences, 9 (3): 256—278, doi:10.1016/S0022-0000(74)80044-9, MR 0449012
19. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Exercise 35.3-3. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. с. 1122. ISBN 0-262-03384-4.
20. Brown, R. (Жовтень 1988), Календарні черги: швидка реалізація черги пріоритетів ${\displaystyle O(1)}$ для задачі симуляції подій, Communications of the ACM, 31 (10): 1220—1227, doi:10.1145/63039.63045, S2CID 32086497
21. Erickson, K. Bruce; Ladner, Richard E.; LaMarca, Anthony (2000), Оптимізація статичних календарних черг, ACM Transactions on Modeling and Computer Simulation, 10 (3): 179—214, doi:10.1145/361026.361028