Перегляд вихідного коду сторінки Черга на основі відер

{{Картка
|ім'я = Черга на основі відер
|зображення = [[Файл:GWR Fire Buckets, Severn Valley Railway (17351340581).jpg|200px]]
|підпис = Массив відер, придатних для пріоритетів у діапазоні від 1 до 6. Елемент із мінімальним пріоритетом можна знайти в крайньому лівому непорожньому відрі.
|мітка1 = Тип
|текст1 = [[Черга з пріоритетом]]
|мітка2 = Винахідник
|текст2 = Роберт Діал
|мітка3 = Рік винаходу
|текст3 = 1969
|мітка4 = Середня вставка
|текст4 = {{mvar|O}}(1)
|мітка5 = Найгірша вставка
|текст5 = {{mvar|O}}(1)
|мітка6 = Середнє видалення мінімуму
|текст6 = {{mvar|O}}(#пріоритетів)
|мітка7 = Найгірше видалення мінімуму
|текст7 = {{mvar|O}}(#пріоритетів)
|мітка8 = Середнє знаходження мінімуму
|текст8 = {{mvar|O}}(#пріоритетів)
|мітка9 = Найгірше знаходження мінімуму
|текст9 = {{mvar|O}}(#пріоритетів)
|мітка10 = Середнє зменшення ключа
|текст10 = {{mvar|O}}(1)
|мітка11 = Найгірше зменшення ключа
|текст11 = {{mvar|O}}(1)
}}

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

Черга на основі відер є аналогом пріоритетної черги для [[Сортування Діріхле]] (також відомого як сортування за відрами), алгоритму сортування, що розміщує елементи у відра, індексовані за пріоритетами, а потім об'єднує ці відра. Використання черги на основі відер як пріоритетної черги у [[сортування вибором]] призводить до варіації алгоритму сортування за відрами.<ref name=figueira/> Черги на основі відер також називають '''чергами пріоритетів на основі відер'''<ref name=hns/> або '''чергами пріоритетів із обмеженою висотою'''.<ref name="skiena"/> Якщо їх використовують для квантованих наближень до [[дійсне число|дійсних чисел]] у якості пріоритетів, їх також називають '''неупорядкованими чергами пріоритетів'''<ref name=remarks>{{cite web|last1=Rasch|first1=Christian|last2=Satzger|first2=Thomas|doi=10.1093/imanum/drm028|issue=3|journal=IMA Journal of Numerical Analysis|mr=2520171|pages=806–813|title=Remarks on the {{math|''O''(''N'')}} implementation of the fast marching method|url=http://pcbornemann4.ma.tum.de/foswiki/pub/M3/Allgemeines/Publications/drm028v1.pdf|volume=29|year=2009}}</ref> або '''псевдо чергами пріоритетів'''.<ref name=pseudo/> Вони тісно пов'язані з [[календарна черга|календарною чергою]], структурою, яка використовує подібний масив відер для точного пріоритизації за дійсними числами.

Застосування черги на основі відер включає обчислення [[Виродженість (теорія графів)|дегенерації графа]], швидкі [[алгоритм]]и для [[Задача про найкоротший шлях|найкоротших шляхів]] та [[Задача про найширший шлях|найширших шляхів]] для графів з вагами, що є малими цілими числами або вже впорядковані, а також жадібні [[Апроксимаційний алгоритм|апроксимаційні алгоритми]] для [[Задача про покриття множини|задачі покриття множини]]. Квантована версія цієї структури також застосовувалася для [[Планувальник операційної системи|планування]]<ref name=figueira/> та для [[marching cubes]] у [[комп'ютерна графіка|комп'ютерній графіці]].<ref name=remarks/> Перше використання черги на основі відер<ref name=es>{{cite book|title=Heuristic Search: Theory and Applications|first1=Stefan|last1=Edelkamp|first2=Stefan|last2=Schroedl|publisher=Elsevier|year=2011|contribution=3.1.1 Структури даних на основі відер|pages=90–92|contribution-url=https://books.google.com/books?id=3k5MVjKzBP4C&pg=PA90|isbn=9780080919737}}. Див. також с.&nbsp;157 для історії та назви цієї структури.</ref> було в алгоритмі пошуку найкоротшого шляху, запропонованому {{harvtxt|Dial|1969}}.<ref name=dial>{{cite journal
 | last = Dial | first = Robert B.
 | doi = 10.1145/363269.363610
 | issue = 11
 | journal = [[Communications of the ACM]]
 | pages = 632–633
 | title = Algorithm 360: Shortest-path forest with topological ordering [H]
 | volume = 12
 | year = 1969| s2cid = 6754003
 | doi-access = free
 }}.</ref>

== Операція ==

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

Черга на основі відер може обробляти елементи з цілими пріоритетами в діапазоні від 0 або 1 до відомої межі {{mvar|C}} та виконувати операції вставки елементів, зміни пріоритету елементів або витягання (пошук та видалення) елемента з мінімальним (або максимальним) пріоритетом. Вона складається з масиву {{mvar|A}} [[Контейнер (абстрактний тип даних)|структур даних-контейнерів]]; у більшості джерел ці контейнери є [[Двобічно зв'язаний список|двонаправленими списками]], але вони можуть бути також [[Динамічний масив|динамічними масивами]]<ref name=hns>{{cite conference
 | last1 = Хенцінгер | first1 = Моніка | author1-link = Monika Henzinger
 | last2 = Ное | first2 = Александер
 | last3 = Шульц | first3 = Крістіан
 | arxiv = 1808.05458
 | contribution = Розподілені мінімальні точні розрізи в спільній пам'яті
 | doi = 10.1109/IPDPS.2019.00013
 | pages = 13–22
 | title = 2019 IEEE Міжнародний симпозіум з розподіленої та паралельної обробки, IPDPS 2019, Ріо-де-Жанейро, Бразилія, 20-24 травня 2019
 | year = 2019| s2cid = 52019258 }}</ref> або [[Множина (структура даних)|динамічними множинами]]. Контейнер у {{mvar|p}}-тій комірці масиву {{math|''A''[''p'']}} зберігає колекцію елементів, чий пріоритет дорівнює {{mvar|p}}.

Черга на основі відер може виконувати наступні операції:
* Щоб вставити елемент {{mvar|x}} з пріоритетом {{mvar|p}}, додайте {{mvar|x}} до контейнера в {{math|''A''[''p'']}}.
* Щоб змінити пріоритет елемента, видаліть його з контейнера старого пріоритету і повторно вставте його в контейнер нового пріоритету.
* Щоб витягти елемент з мінімальним або максимальним пріоритетом, виконайте [[лінійний пошук]] в масиві, щоб знайти перший або останній непорожній контейнер відповідно, виберіть довільний елемент з цього контейнера і видаліть його з контейнера.
Таким чином, вставка та зміна пріоритетів займають постійний час, а витягування елемента з мінімальним або максимальним пріоритетом займає час {{math|''O''(''C'')}}.<ref name="skiena">{{citation|title=Посібник з проектування алгоритмів|first=Стівен С.|last=Скієна|authorlink=Steven Skiena|publisher=Springer|year=1998|isbn=9780387948607|page=181|url=https://books.google.com/books?id=TrXd-gxPhVYC&pg=PA181}}.</ref><ref name=es/><ref name="ms">{{citation|title=Алгоритми та структури даних: Основний набір інструментів|first1=Курт|last1=Мехльгорн|author1-link=Kurt Mehlhorn|first2=Пітер|last2=Сандерс|author2-link=Peter Sanders (computer scientist)|publisher=Springer|year=2008|isbn=9783540779773|contribution=10.5.1 Черги на основі відер|page=201|contribution-url=https://books.google.com/books?id=oK3UWxg_UhsC&pg=PA201}}.</ref>

=== Оптимізації ===
Як оптимізацію, структура даних може починати кожний послідовний пошук непорожнього відра з останнього знайденого непорожнього відра замість початку масиву. Це можна зробити одним з двох способів: лінивим (затримуючи ці послідовні пошуки до їхньої необхідності) або завчасним (здійснюючи пошуки заздалегідь). Вибір часу для виконання пошуку впливає на те, яка з операцій структури даних сповільнюється цими пошуками. Оригінальна версія структури Дайла використовувала лінивий пошук. Це можна реалізувати, підтримуючи індекс {{mvar|L}}, який є [[нижня межа]] мінімального пріоритету будь-якого елемента, що зараз знаходиться в черзі. При вставці нового елемента {{mvar|L}} слід оновити до мінімального з його старого значення і нового пріоритету елемента. При пошуку елемента з мінімальним пріоритетом пошук можна почати з {{mvar|L}} замість з нуля, і після пошуку {{mvar|L}} слід залишити рівним пріоритету, знайденому під час пошуку.<ref name=dial/><ref name=bertsekas/> Альтернативно, завчасна версія цієї оптимізації підтримує {{mvar|L}} оновленим так, щоб він завжди вказував на перше непорожнє відро. При вставці нового елемента з пріоритетом меншим ніж {{mvar|L}}, структура даних встановлює {{mvar|L}} на новий пріоритет, а при видаленні останнього елемента з відра з пріоритетом {{mvar|L}}, виконується послідовний пошук через більші індекси до знаходження непорожнього відра і встановлення {{mvar|L}} на пріоритет отриманого відра.<ref name="skiena"/>

В обох цих варіаціях кожний послідовний пошук займає час, пропорційний різниці між старим і новим значенням {{mvar|L}}. Це може бути значно швидше, ніж межа часу {{math|''O''(''C'')}} для пошуків у не оптимізованій версії структури даних. У багатьох застосуваннях пріоритетних черг, таких як [[алгоритм Дейкстри]], мінімальні пріоритети формують [[монотонна послідовність]], що дозволяє використовувати [[монотонну пріоритетну чергу]]. У цих застосуваннях, як для лінивих, так і для завчасних варіацій оптимізованої структури, послідовні пошуки непорожніх відер охоплюють неперетинні діапазони відер. Оскільки кожне відро входить максимум до одного з цих діапазонів, кількість їх кроків разом не перевищує {{mvar|C}}. Тому, у цих застосуваннях, загальний час для послідовності з {{mvar|n}} операцій становить {{math|''O''(''n'' + ''C'')}}, а не повільніша межа часу {{math|''O''(''nC'')}} яка б виникла без цієї оптимізації.<ref name=bertsekas/> Відповідну оптимізацію можна застосувати в додатках, де черга з відрами використовується для знаходження елементів з максимальним пріоритетом, але в цьому випадку слід підтримувати індекс, який встановлює верхню межу для максимального пріоритету, а послідовний пошук непорожнього відра слід проводити вниз від цієї верхньої межі.<ref name=lmw/>
Ще одна оптимізація (запропонована {{harvnb|Dial|1969}}) може бути використана для економії простору, коли пріоритети є монотонними і, протягом алгоритму, завжди потрапляють у діапазон {{mvar|r}} значень, а не розтягуються на весь діапазон від 0 до {{mvar|C}}. У цьому випадку можна індексувати масив за пріоритетами по модулю {{mvar|r}}, а не за їхніми фактичними значеннями. Пошук елемента з мінімальним пріоритетом слід завжди починати з попереднього мінімуму, щоб уникнути пріоритетів, які вищі за мінімум, але мають менші модулі. Зокрема, ця ідея може бути застосована в алгоритмі Дейкстри для графів, у яких довжини ребер є цілими числами в діапазоні від 1 до {{mvar|r}}.{{r|ms}}

Оскільки створення нової черги з відрами передбачає ініціалізацію масиву порожніх відер, цей крок ініціалізації займає час, пропорційний кількості пріоритетів. Варіація черги з відрами, описана {{li|Donald B. Johnson|Q=Q5293994}} у 1981 році, натомість зберігає тільки непорожні відра у зв'язаному списку, відсортованому за їхніми пріоритетами, і використовує допоміжне дерево пошуку для швидкого знаходження позиції в цьому зв'язаному списку для будь-яких нових відер. Ініціалізація цієї варіантної структури займає час {{math|''O''(log log ''C'')}}, знаходження елемента з мінімальним або максимальним пріоритетом займає константний час, а вставка або видалення елемента займає час {{math|''O''(log log ''D'')}}, де {{mvar|D}}&nbsp;— різниця між найближчими меншими та більшими пріоритетами до пріоритету вставленого або видаленого елемента.<ref>{{citation
 | last = Johnson | first = Donald B. | author-link = Donald B. Johnson
 | doi = 10.1007/BF01786986
 | issue = 4
 | journal = [[Mathematical Systems Theory]]
 | mr = 683047
 | pages = 295–309
 | title = Черга з пріоритетами, в якій ініціалізація та операції черги займають час {{math|''O''(log log ''D'')}}
 | volume = 15
 | year = 1981| s2cid = 35703411 }}</ref>

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

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

=== Дегерація графа ===
Через чергу відер можна підтримувати [[Вершина (теорія графів)|вершини]] [[Граф (математика)|ненаправленого графа]], пріоритетизуючи їх за [[Степінь вершини (теорія графів)|ступенем]], і повторно знаходити та видаляти вершину з мінімальним ступенем.<ref name="skiena"/> Цей [[жадібний алгоритм]] можна використовувати для обчислення [[Виродженість (теорія графів)|дегерації]] даного графа, яка дорівнює найбільшому ступеню будь-якої вершини на момент її видалення. Алгоритм виконується за [[Часова складність|лінійний час]], з оптимізацією або без неї, яка підтримує нижню межу на мінімальний пріоритет, оскільки кожна вершина знаходиться за час, пропорційний її ступеню, і сума всіх ступенів вершин є лінійною відносно кількості ребер графа.<ref>{{citation
 | last1 = Matula | first1 = David W. | author1-link = David Matula
 | last2 = Beck | first2 = L. L. 
 | doi = 10.1145/2402.322385
 | journal = [[Journal of the ACM]]
 | volume = 30
 | mr = 0709826
 | number = 3
 | pages = 417–427
 | title = Smallest-last ordering and clustering and graph coloring algorithms
 | year = 1983| s2cid = 4417741 | doi-access = free
 }}.</ref>

=== Алгоритм Дайла для найкоротших шляхів ===
У алгоритмі Дейкстри для [[найкоротший шлях]]ів у [[орієнтований граф]]ах з вагами ребер, що є додатними цілими числами, пріоритети є монотонними,<ref name=varghese>{{citation|title=Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices|first=George|last=Varghese|authorlink=George Varghese|publisher=Morgan Kaufmann|year=2005|isbn=9780120884773|pages=78–80|url=https://books.google.com/books?id=fnZ9WWpVK7oC&pg=PA78}}.</ref> і монотонну чергу відер можна використовувати для досягнення часових меж {{math|''O''(''m'' + ''dc'')}}, де {{mvar|m}}&nbsp;— кількість ребер, {{mvar|d}}&nbsp;— діаметр мережі, а {{mvar|c}}&nbsp;— максимальна (ціла) вартість зв'язку.<ref name=bertsekas/><ref name=festa>{{citation
 | last = Festa | first = Paola
 | editor1-last = Resende | editor1-first = Mauricio G. C. | editor1-link = Mauricio Resende
 | editor2-last = Pardalos | editor2-first = Panos M. | editor2-link = Panos M. Pardalos
 | contribution = Shortest path algorithms
 | doi = 10.1007/978-0-387-30165-5_8
 | location = Boston
 | pages = 185–210
 | publisher = Springer
 | title = Handbook of Optimization in Telecommunications
 | year = 2006}}; див. зокрема розділ 8.3.3.6, «Реалізація Дайла», с. 194—195.</ref> Цей варіант алгоритму Дейкстри також відомий як [[алгоритм Дайла]],<ref name=bertsekas>{{citation|last=Bertsekas|first=Dimitri P.|author-link=Dimitri Bertsekas|contribution=Dial's algorithm|contribution-url=https://books.google.com/books?id=7i3XQVNkJqIC&pg=PA72|isbn=0-262-02334-2|location=Cambridge, Massachusetts|mr=1201582|pages=72–75|publisher=MIT Press|title=Linear Network Optimization: Algorithms And Codes|year=1991}}</ref> на честь Роберта Б. Дайла, який опублікував його в 1969 році.<ref name=dial/> Та сама ідея також працює, використовуючи квантовану чергу відер, для графів з додатніми дійсними вагами ребер, коли співвідношення максимального до мінімального ваги не перевищує {{mvar|c}}.<ref>{{harvtxt|Mehlhorn|Sanders|2008}} (Завдання 10.11, с. 201) приписують цю ідею статті 1978 року Е.&nbsp;А.&nbsp;Диница (Єфим Динітц).</ref> У цій квантованій версії алгоритму вершини обробляються не в порядку, порівняно з результатом, отриманим з не квантованою чергою пріоритетів, але правильні найкоротші шляхи все ще знаходяться.<ref name=pseudo>{{citation|last1=Robledo|first1=Alicia|last2=Guivant|first2=José E.|editor1-last=Wyeth|editor1-first=Gordon|editor2-last=Upcroft|editor2-first=Ben|contribution=Pseudo priority queues for real-time performance on dynamic programming processes applied to path planning|contribution-url=https://www.araa.asn.au/acra/acra2010/papers/pap144s1-file1.pdf|title=Australasian Conference on Robotics and Automation|year=2010}}</ref> У цих алгоритмах пріоритети будуть охоплювати лише діапазон шириною {{math|''c'' + 1}}, тому модульна оптимізація може бути використана для зменшення простору до {{math|''O''(''n'' + ''c'')}}.<ref name="ms"/><ref name=festa/>

Варіант того ж алгоритму можна використовувати для [[Задача про найширший шлях|проблема найширшого шляху]]. У поєднанні з методами швидкого розподілу нецілих ваг ребер на підмножини, які можна присвоїти цілі пріоритети, це призводить до майже лінійних рішень для версії найширшого шляху з одного джерела до однієї мети.<ref>{{citation
 | last1 = Gabow | first1 = Harold N. | author1-link = Harold N. Gabow
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | doi = 10.1016/0196-6774(88)90031-4
 | mr = 955149
 | issue = 3
 | journal = Journal of Algorithms
 | pages = 411–417
 | title = Algorithms for two bottleneck optimization problems
 | volume = 9
 | year = 1988| url = https://zenodo.org/record/1258419
 }}</ref>

=== Жадібне покриття множин ===
[[Задача про покриття множини|Проблема покриття множин]] має на вході [[сімейство множин]]. Виходом повинна бути підмножина цих множин з такою ж об'єднанням, як у вихідної сім'ї, що містить якомога менше множин. Це [[NP-складна задача|NP-складна проблема]], але має [[Задача про покриття множини#Жадібний наближений алгоритм|жадібний наближувальний алгоритм]], який досягає логарифмічної апроксимації, що є в основному найкращим можливим варіантом, якщо [[Рівність класів P і NP|P ≠ NP]].<ref>{{citation
 | last1 = Dinur | first1 = Irit | author1-link = Irit Dinur
 | last2 = Steurer | first2 = David
 | editor-last = Shmoys | editor-first = David B. | editor-link = David Shmoys
 | contribution = Аналіз підходу до паралельного повторення
 | doi = 10.1145/2591796.2591884
 | mr = 3238990
 | pages = 624–633
 | publisher = ACM
 | title = Симпозіум з теорії обчислень, STOC 2014, Нью-Йорк, США, 31 травня - 3 червня 2014 року
 | year = 2014| arxiv = 1305.1979
 | s2cid = 15252482 }}</ref> Цей наближувальний алгоритм вибирає свою підмножину, постійно обираючи множину, яка покриває максимальну кількість залишкових непокритих елементів.<ref>{{citation
 | last = Johnson | first = David S. | author-link = David S. Johnson
 | doi = 10.1016/S0022-0000(74)80044-9
 | journal = [[Journal of Computer and System Sciences]]
 | mr = 449012
 | pages = 256–278
 | title = Наближувальні алгоритми для комбінаторних проблем
 | volume = 9
 | year = 1974| issue = 3 | doi-access = 
 }}</ref> Стандартне завдання з проектування алгоритмів вимагає реалізації цього алгоритму, яка займає лінійний час від розміру входу, що є сумою розмірів усіх вхідних множин.<ref>{{Introduction to Algorithms|edition=3|chapter=Exercise 35.3-3|pages=1122|mode=cs2}}</ref>

Цю задачу можна вирішити за допомогою черги відер множин у вхідній сім'ї, пріоритетизованих за кількістю залишкових елементів, які вони покривають. Щоразу, коли жадібний алгоритм вибирає множину як частину свого виходу, нові покриті елементи множини повинні бути відняті з пріоритетів інших множин, що їх покривають; протягом алгоритму кількість цих змін пріоритетів дорівнює просто сумі розмірів вхідних множин. Пріоритети є монотонно зменшувальними цілими числами, верхня межа яких визначається кількістю елементів, які потрібно покрити. Кожен вибір жадібного алгоритму включає знаходження множини з максимальним пріоритетом, що можна зробити, скануючи вниз через відра черги відер, починаючи з найостаннішого попереднього максимального значення. Загальний час є лінійним від розміру входу.<ref name=lmw>{{citation
 | last1 = Lim | first1 = C. L.
 | last2 = Moffat | first2 = Alistair
 | last3 = Wirth | first3 = Anthony Ian
 | editor1-last = Thomas | editor1-first = Bruce
 | editor2-last = Parry | editor2-first = Dave
 | contribution = Ліниві та жадібні підходи до задачі покриття множин
 | contribution-url = https://crpit.scem.westernsydney.edu.au/abstracts/CRPITV147Lim.html
 | pages = 19–27
 | publisher = Австралійське комп'ютерне товариство
 | series = CRPIT
 | title = Тридцять сьома Австралійська конференція з комп'ютерних наук, ACSC 2014, Окленд, Нова Зеландія, січень 2014 року
 | volume = 147
 | year = 2014}}</ref> Див. зокрема Розділ 2.4, «Черга пріоритетів», с. 22.

=== Планування ===
Черги відер можна використовувати для планування завдань з термінами виконання, наприклад, в [[Пакетна передача даних|пакетна передача]] для інтернет-даних з гарантіями [[QoS|якість обслуговування]]. Для цього застосування терміни виконання повинні бути квантизовані в дискретні інтервали, і завдання, терміни виконання яких потрапляють в один і той же інтервал, вважаються такими, що мають однаковий пріоритет.<ref name=figueira>{{citation
 | last = Figueira | first = N. R.
 | contribution = Рішення задачі черги пріоритетів для дисциплін обслуговування за термінами
 | doi = 10.1109/icccn.1997.623330
 | pages = 320–325
 | publisher = IEEE Computer Society Press
 | title = Матеріали шостої міжнародної конференції з комп'ютерних комунікацій і мереж
 | year = 1997| s2cid = 5611516
 }}</ref>

Варіація квантизованої структури даних черги відер, [[календарна черга]], була застосована для планування [[Дискретно-подійне моделювання|дискретно-подійних симуляцій]], де елементи в черзі є майбутніми подіями, пріоритетизованими за часом у симуляції, коли події повинні відбутися. У цьому застосуванні порядок подій є критичним, тому пріоритети не можуть бути апроксимовані. Тому календарна черга виконує пошуки елемента з мінімальним пріоритетом інакше ніж черга відер: у черзі відер будь-який елемент першого непорожнього відра може бути повернутий, але календарна черга замість цього шукає всі елементи в цьому відрі, щоб визначити, який з них має найменший не квантизований пріоритет. Щоб ці пошуки залишалися швидкими, ця варіація намагається підтримувати кількість відер пропорційною кількості елементів, шляхом коригування масштабу квантизації та перебудови структури даних, коли вона виходить з балансу. Календарні черги можуть бути повільнішими за черги відер у найгіршому випадку (коли багато елементів потрапляють в одне й те саме найменше відро), але є швидкими, коли елементи рівномірно розподілені між відрами, що призводить до постійного середнього розміру відра.<ref>{{citation
 | last = Brown | first = R.
 | date = Жовтень 1988
 | doi = 10.1145/63039.63045
 | issue = 10
 | journal = [[Communications of the ACM]]
 | pages = 1220–1227
 | title = Календарні черги: швидка реалізація черги пріоритетів <math>O(1)</math> для задачі симуляції подій
 | volume = 31| s2cid = 32086497
 | doi-access = free
 }}</ref><ref>{{citation
 | last1 = Erickson | first1 = K. Bruce
 | last2 = Ladner | first2 = Richard E. | author2-link = Richard E. Ladner
 | last3 = LaMarca | first3 = Anthony
 | doi = 10.1145/361026.361028
 | issue = 3
 | journal = ACM Transactions on Modeling and Computer Simulation
 | pages = 179–214
 | title = Оптимізація статичних календарних черг
 | volume = 10
 | year = 2000| doi-access = free
 }}</ref>

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

== Див. також ==
* {{li|Soft heap|Q=Q7553986}}, інший спосіб прискорення черг пріоритетів шляхом використання апроксимованих пріоритетів

== Примітки ==
{{reflist}}

[[Категорія:Черги з пріоритетом]]