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

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

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

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

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

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

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

Монотонні пріоритетні черги - це спеціалізовані черги, які оптимізовані для випадку, коли не вставляється жоден елемент, що має нижчий пріоритет (у випадку 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;
	}
};