Черга з пріоритетом

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Сучасніші реалізації можуть підтримувати складніші операції, такі як 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;
	}
};

Див. також

[ред. | ред. код]

Література

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