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

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

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

Застосування черги на основі відер включає обчислення дегенерації графа, швидкі алгоритми для найкоротших шляхів та найширших шляхів для графів з вагами, що є малими цілими числами або вже впорядковані, а також жадібні апроксимаційні алгоритми для задачі покриття множини. Квантована версія цієї структури також застосовувалася для планування та для marching cubes у комп'ютерній графіці. Перше використання черги на основі відер було в алгоритмі пошуку найкоротшого шляху, запропонованому Шаблон:Harvtxt.

Операція

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

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

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

• Щоб вставити елемент Шаблон:Mvar з пріоритетом Шаблон:Mvar, додайте Шаблон:Mvar до контейнера в Шаблон:Math.
• Щоб змінити пріоритет елемента, видаліть його з контейнера старого пріоритету і повторно вставте його в контейнер нового пріоритету.
• Щоб витягти елемент з мінімальним або максимальним пріоритетом, виконайте лінійний пошук в масиві, щоб знайти перший або останній непорожній контейнер відповідно, виберіть довільний елемент з цього контейнера і видаліть його з контейнера.

Таким чином, вставка та зміна пріоритетів займають постійний час, а витягування елемента з мінімальним або максимальним пріоритетом займає час Шаблон:Math.

Оптимізації

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

В обох цих варіаціях кожний послідовний пошук займає час, пропорційний різниці між старим і новим значенням Шаблон:Mvar. Це може бути значно швидше, ніж межа часу Шаблон:Math для пошуків у не оптимізованій версії структури даних. У багатьох застосуваннях пріоритетних черг, таких як алгоритм Дейкстри, мінімальні пріоритети формують монотонна послідовність, що дозволяє використовувати монотонну пріоритетну чергу. У цих застосуваннях, як для лінивих, так і для завчасних варіацій оптимізованої структури, послідовні пошуки непорожніх відер охоплюють неперетинні діапазони відер. Оскільки кожне відро входить максимум до одного з цих діапазонів, кількість їх кроків разом не перевищує Шаблон:Mvar. Тому, у цих застосуваннях, загальний час для послідовності з Шаблон:Mvar операцій становить Шаблон:Math, а не повільніша межа часу Шаблон:Math яка б виникла без цієї оптимізації. Відповідну оптимізацію можна застосувати в додатках, де черга з відрами використовується для знаходження елементів з максимальним пріоритетом, але в цьому випадку слід підтримувати індекс, який встановлює верхню межу для максимального пріоритету, а послідовний пошук непорожнього відра слід проводити вниз від цієї верхньої межі. Ще одна оптимізація (запропонована Шаблон:Harvnb) може бути використана для економії простору, коли пріоритети є монотонними і, протягом алгоритму, завжди потрапляють у діапазон Шаблон:Mvar значень, а не розтягуються на весь діапазон від 0 до Шаблон:Mvar. У цьому випадку можна індексувати масив за пріоритетами по модулю Шаблон:Mvar, а не за їхніми фактичними значеннями. Пошук елемента з мінімальним пріоритетом слід завжди починати з попереднього мінімуму, щоб уникнути пріоритетів, які вищі за мінімум, але мають менші модулі. Зокрема, ця ідея може бути застосована в алгоритмі Дейкстри для графів, у яких довжини ребер є цілими числами в діапазоні від 1 до Шаблон:Mvar.Шаблон:R

Оскільки створення нової черги з відрами передбачає ініціалізацію масиву порожніх відер, цей крок ініціалізації займає час, пропорційний кількості пріоритетів. Варіація черги з відрами, описана Шаблон:Li у 1981 році, натомість зберігає тільки непорожні відра у зв'язаному списку, відсортованому за їхніми пріоритетами, і використовує допоміжне дерево пошуку для швидкого знаходження позиції в цьому зв'язаному списку для будь-яких нових відер. Ініціалізація цієї варіантної структури займає час Шаблон:Math, знаходження елемента з мінімальним або максимальним пріоритетом займає константний час, а вставка або видалення елемента займає час Шаблон:Math, де Шаблон:Mvar — різниця між найближчими меншими та більшими пріоритетами до пріоритету вставленого або видаленого елемента.

Приклад

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

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

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

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

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

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

У алгоритмі Дейкстри для найкоротший шляхів у орієнтований графах з вагами ребер, що є додатними цілими числами, пріоритети є монотонними, і монотонну чергу відер можна використовувати для досягнення часових меж Шаблон:Math, де Шаблон:Mvar — кількість ребер, Шаблон:Mvar — діаметр мережі, а Шаблон:Mvar — максимальна (ціла) вартість зв'язку. Цей варіант алгоритму Дейкстри також відомий як алгоритм Дайла, на честь Роберта Б. Дайла, який опублікував його в 1969 році. Та сама ідея також працює, використовуючи квантовану чергу відер, для графів з додатніми дійсними вагами ребер, коли співвідношення максимального до мінімального ваги не перевищує Шаблон:Mvar. У цій квантованій версії алгоритму вершини обробляються не в порядку, порівняно з результатом, отриманим з не квантованою чергою пріоритетів, але правильні найкоротші шляхи все ще знаходяться. У цих алгоритмах пріоритети будуть охоплювати лише діапазон шириною Шаблон:Math, тому модульна оптимізація може бути використана для зменшення простору до Шаблон:Math.

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

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

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

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

Планування

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

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

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

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

Див. також

• Шаблон:Li, інший спосіб прискорення черг пріоритетів шляхом використання апроксимованих пріоритетів