Черга з пріоритетами англ priority queue це структура даних що призначена для обслуговування множини елементів кожний з

Черга з пріоритетами (англ. priority queue) — це структура даних, що призначена для обслуговування множини елементів, кожний з яких додатково має "пріоритет", пов'язаний з ним. У пріоритетній черзі першим обслуговується елемент, який має найвищий пріоритет, відповідно елемент, що має найнижчий пріоритет буде обслугований останнім. У деяких реалізаціях, якщо два елементи мають однаковий пріоритет, вони подаються відповідно до порядку, в якому вони були закладені, в той час як в інших реалізаціях упорядкування елементів з однаковим пріоритетом не визначено.

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

Операції

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

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), що повертає елемент з найвищим пріоритетом, але не змінює чергу, часто реалізується, і майже завжди виконується за час $O(1)$ . Ця операція та її продуктивність $O(1)$ мають вирішальне значення для багатьох застосувань пріоритетних черг.

Сучасніші реалізації можуть підтримувати складніші операції, такі як pull_lowest_priority_element, що перевіряє перші кілька елементів з найвищим або найнижчим пріоритетом, очищаючи чергу, очищаючи підмножини черги, виконуючи пакетну вставку, об'єднуючи дві або більше черг в одну, збільшуючи пріоритет будь-якого елемента тощо.

Використання черги з пріоритетом для сортування

З точки зору обчислювальної складності, пріоритетні черги узгоджуються з алгоритмами сортування. Семантика пріоритетних черг, пропонує метод сортування: вставляти всі елементи, які слід сортувати, в чергу пріоритетів, і послідовно видаляти їх, таким чином вони виходитимуть у відсортованому порядку. Насправді це процедура, яка використовується кількома алгоритмами сортування, після видалення рівня абстракції, що надається чергою пріоритету. Цей метод сортування еквівалентний таким алгоритмам сортування:


Назва	Реалізація пріоритетної черги	Найкраща швидкодія	Середня швидкодія	Найгірша швидкодія
(Пірамідальне сортування)	Купа	$n\log(n)$	$n\log(n)$	$n\log(n)$
(Плавне сортування)	Купа Леонардо	$n$	$n\log(n)$	$n\log(n)$
(Сортування вибором)	Невпорядкований масив	$n^{2}$	$n^{2}$	$n^{2}$
(Сортування включенням)	Впорядкований масив	$n$	$n^{2}$	$n^{2}$
(Сортування двійковим деревом)	Збалансоване двійкове дерево пошуку	$n\log(n)$	$n\log(n)$	$n\log(n)$

Реалізація

Прості реалізації

Існує багато простих способів реалізації черги з пріоритетами, проте, як правило, вони не є ефективними. Такі способи допомагають краще зрозуміти, що таке пріоритетна черга. Наприклад, можна зберегти всі елементи в невпорядкованому списку. У цьому випадку кожного разу, щоб отримати елемент з найвищим пріоритетом, потрібно буде виконувати пошук по всіх елементах списку. (У великій O-нотації: $O(1)$ час вставки, $O(n)$ час витягування за рахунок пошуку.)

Звичайна реалізація

Щоб підвищити продуктивність, черги з пріоритетами зазвичай використовують купу як свою магістраль, даючи $O(\log n)$ продуктивність для вставок і вилучень, і $O(n)$ для початкової побудови. Різновиди базових куп, такі як купа сполучень або (купа Фібоначчі), можуть надати кращі асимптотичні розміри для деяких операцій.

Альтернативно, коли використовується самозбалансоване двійкове дерево пошуку, вставка і видалення також займають час $O(\log n)$ , хоча побудова дерев з існуючих послідовностей елементів займає час $O(n\log n)$ , що характерно, при наявності доступу до цих структур даних, наприклад, із сторонніх або стандартних бібліотек.

Спеціалізовані купи

Існує декілька спеціалізованих структур даних – куп, які або забезпечують додаткові операції, або покращують реалізації на основі куп для конкретних типів ключів, зокрема цілочислових ключів.

Коли набір ключів дорівнює {1, 2, ..., C}, і потрібні лише insert, find-min та extract-min , чергу відра можна сконструювати як масив зв'язаних списків C, з вказівником на верхню частину (спочатку C). Вставка елемента з ключем k додає елемент до k-комірки, і оновлює top ← min (top, k), обидві операції виконуються за сталий час. Extract-min видаляє та повертає один елемент зі списку з вершиною індексу, після чого збільшує вершину, якщо це необхідно, доки він знову не буде вказувати на непустий список. Це займає час $O(C)$ у найгіршому випадку. Такі черги корисні для сортування вершин графу за їхнім степенем.
Для набору ключів {1, 2, ..., C} (дерево ван Емде Боаса) підтримуватиме minimum, maximum, insert, delete, search, extract-min, extract-max, predecessor і successor операції в $O(\log \log C)$ час, але має простір для малих черг близько O(2^m/2) , де m - кількість бітів у значенні пріоритету.
Алгоритм дерева злиття Фредмана і Вілларда реалізує мінімальну операцію за час $O(1)$ і операції insert і extract-min в $O({\sqrt {\log n}})$ час, однак автор стверджує, що: "Наші алгоритми мають лише теоретичний інтерес. Постійні фактори, що беруть участь у часі виконання, виключають практичність".

Для додатків, які виконують багато операцій "peek" для кожної операції "extract-min" складність часу для peek може бути зменшена до $O(1)$ у всіх реалізаціях дерев і куп, кешуванням елементу найвищого пріоритету після кожної вставки і видалення. Для вставки це додає не більше постійної вартості, оскільки знову вставлений елемент порівнюється тільки з раніше кешованим мінімальним елементом. Для видалення це максимум спричинює додаткові витрати, які зазвичай дешевші, ніж вартість видалення, тому на загальну складність часу суттєво не впливає.

Монотонні пріоритетні черги - це спеціалізовані черги, які оптимізовані для випадку, коли не вставляється жоден елемент, що має нижчий пріоритет (у випадку min-heap), ніж будь-який попередньо витягнутий елемент. Це обмеження задовольняється кількома практичними застосуваннями пріоритетних черг.

Приклад реалізації

Приклад реалізації пріоритетної черги на за допомогою двозв'язного списку:

#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; } };

Див. також

Література

Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Section 6.5: Черги з пріоритетами. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .

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