Черга з пріоритетами () — це структура даних, що призначена для обслуговування множини елементів, кожний з яких додатково має "пріоритет", пов'язаний з ним. У пріоритетній черзі першим обслуговується елемент, який має найвищий пріоритет, відповідно елемент, що має найнижчий пріоритет буде обслугований останнім. У деяких реалізаціях, якщо два елементи мають однаковий пріоритет, вони подаються відповідно до порядку, в якому вони були закладені, в той час як в інших реалізаціях упорядкування елементів з однаковим пріоритетом не визначено.
Хоча черги з пріоритетами часто реалізуються купами, вони концептуально відрізняються від них. Черга пріоритетів - це абстрактне поняття, як "список" або "карта"; так само, як список може бути реалізована зв'язаним списком або масивом, черга з пріоритетом може бути реалізована купою або безліччю інших методів, таких як невпорядкований масив.
Операції Черга з пріоритетами повинна підтримувати принаймні такі операції:
is_empty: перевіряє, чи черга порожня. insert_with_priority: додає елемент до черги з відповідним йому пріоритетом. pull_highest_priority_element: вилучає з черги елемент, що має найвищий пріоритет, повертаючи його.
Інші назви: "pop_element (Off)", "get_maximum_element" або "get_front (most) _element".
Деякі конвенції змінюють порядок пріоритетів, вважаючи, що менші значення мають вищий пріоритет, тому це може бути відоме як "get_minimum_element", і часто в літературі називається "get-min".
Також цю операцію можна замінити двома окремими функціями: "peek_at_highest_priority_element" і "delete_element", які можуть бути об'єднані для створення "pull_highest_priority_element".Крім того, peek (у цьому контексті часто називається find-max або find-min), що повертає елемент з найвищим пріоритетом, але не змінює чергу, часто реалізується, і майже завжди виконується за час . Ця операція та її продуктивність мають вирішальне значення для багатьох застосувань пріоритетних черг.
Сучасніші реалізації можуть підтримувати складніші операції, такі як pull_lowest_priority_element, що перевіряє перші кілька елементів з найвищим або найнижчим пріоритетом, очищаючи чергу, очищаючи підмножини черги, виконуючи пакетну вставку, об'єднуючи дві або більше черг в одну, збільшуючи пріоритет будь-якого елемента тощо.
Використання черги з пріоритетом для сортування З точки зору обчислювальної складності, пріоритетні черги узгоджуються з алгоритмами сортування. Семантика пріоритетних черг, пропонує метод сортування: вставляти всі елементи, які слід сортувати, в чергу пріоритетів, і послідовно видаляти їх, таким чином вони виходитимуть у відсортованому порядку. Насправді це процедура, яка використовується кількома алгоритмами сортування, після видалення рівня абстракції, що надається чергою пріоритету. Цей метод сортування еквівалентний таким алгоритмам сортування: +НазваРеалізація пріоритетної чергиНайкраща швидкодіяСередня швидкодіяНайгірша швидкодіяПірамідальне сортуванняКупаПлавне сортуванняКупа ЛеонардоСортування виборомНевпорядкований масивСортування включеннямВпорядкований масивСортування двійковим деревомЗбалансоване двійкове дерево пошуку
Реалізація
Прості реалізації Існує багато простих способів реалізації черги з пріоритетами, проте, як правило, вони не є ефективними. Такі способи допомагають краще зрозуміти, що таке пріоритетна черга. Наприклад, можна зберегти всі елементи в невпорядкованому списку. У цьому випадку кожного разу, щоб отримати елемент з найвищим пріоритетом, потрібно буде виконувати пошук по всіх елементах списку. (У великій O-нотації: час вставки, час витягування за рахунок пошуку.)
Звичайна реалізація Щоб підвищити продуктивність, черги з пріоритетами зазвичай використовують купу як свою магістраль, даючи продуктивність для вставок і вилучень, і для початкової побудови. Різновиди базових куп, такі як купа сполучень або купа Фібоначчі, можуть надати кращі асимптотичні розміри для деяких операцій.
Альтернативно, коли використовується самозбалансоване двійкове дерево пошуку, вставка і видалення також займають час , хоча побудова дерев з існуючих послідовностей елементів займає час , що характерно, при наявності доступу до цих структур даних, наприклад, із сторонніх або стандартних бібліотек.
Спеціалізовані купи Існує декілька спеціалізованих структур даних – куп, які або забезпечують додаткові операції, або покращують реалізації на основі куп для конкретних типів ключів, зокрема цілочислових ключів.
Коли набір ключів дорівнює {1, 2, ..., C}, і потрібні лише insert, find-min та extract-min , чергу відра можна сконструювати як масив зв'язаних списків C, з вказівником на верхню частину (спочатку C). Вставка елемента з ключем k додає елемент до k-комірки, і оновлює top ← min (top, k), обидві операції виконуються за сталий час. Extract-min видаляє та повертає один елемент зі списку з вершиною індексу, після чого збільшує вершину, якщо це необхідно, доки він знову не буде вказувати на непустий список. Це займає час у найгіршому випадку. Такі черги корисні для сортування вершин графу за їхнім степенем. Для набору ключів {1, 2, ..., C} дерево ван Емде Боаса підтримуватиме minimum, maximum, insert, delete, search, extract-min, extract-max, predecessor і successor операції в час, але має простір для малих черг близько O(2m/2) , де m - кількість бітів у значенні пріоритету. Алгоритм дерева злиття Фредмана і Вілларда реалізує мінімальну операцію за час і операції insert і extract-min в час, однак автор стверджує, що: "Наші алгоритми мають лише теоретичний інтерес. Постійні фактори, що беруть участь у часі виконання, виключають практичність".
Для додатків, які виконують багато операцій "peek" для кожної операції "extract-min" складність часу для peek може бути зменшена до у всіх реалізаціях дерев і куп, кешуванням елементу найвищого пріоритету після кожної вставки і видалення. Для вставки це додає не більше постійної вартості, оскільки знову вставлений елемент порівнюється тільки з раніше кешованим мінімальним елементом. Для видалення це максимум спричинює додаткові витрати, які зазвичай дешевші, ніж вартість видалення, тому на загальну складність часу суттєво не впливає.
Монотонні пріоритетні черги - це спеціалізовані черги, які оптимізовані для випадку, коли не вставляється жоден елемент, що має нижчий пріоритет (у випадку min-heap), ніж будь-який попередньо витягнутий елемент. Це обмеження задовольняється кількома практичними застосуваннями пріоритетних черг.
Приклад реалізації
Приклад реалізації пріоритетної черги на C++ за допомогою двозв'язного списку:#include <iostream> #include <list> using namespace std;
struct Pair { char value; size_t priority; Pair(char v, size_t p): value(v), priority(p)
class PriorityQueue { list<Pair> queue; public: void enqueue(Pair elem) { for (auto it = queue.begin(); it != queue.end(); ++it)
if (it->priority > elem.priority)
queue.insert(it, elem); return;
queue.push_back(elem); } char dequeue() { char result = queue.front().value; queue.erase(queue.begin()); return result; } size_t size() { return queue.size(); } char top() { return queue.front().value; } bool isEmpty() { return queue.size() == 0;
Див. також Черга (структура даних) Стек Список (абстрактний тип даних) Масив (структура даних) Купа (структура даних) Алгоритми сортування Асоціативний масив
Література