2.1 Основные подходы к реализации очередей

Перед тем как рассматривать способы реализации очереди, определим требуемые операции, и изобразим схематично на рисунках 2.1-2.3:

1) Вставка в конец

Рисунок 2.1 – Вставка в очередь

2) Удаление из начала

Рисунок 2.2 – Удаление из очереди

3) Получение значения первого элемента

4) Слияние двух очередей

Рисунок 2.3 – Слияние двух очередей

Основными структурами данных, на которой строятся очереди, являются массивы и связные списки. Реализация на массиве повышает производительность и экономит расход ресурсов, однако усложняет работу очереди в вырожденных случаях (операции вставки и удаления не равновероятны). Наиболее предпочтительны реализации на связных списках.

Оценим быстродействие всех операций для достаточно удачной реализации очереди – с помощью связного списка в сравнении с реализацией на массиве.

Основа очереди	Вставка	Удаление	Получение первого элемента	Слияние
Связный список	O(1)	O(1)	O(1)	O(1)
Массив	O (1)	O (n), O(1) если вместо удаления запоминать левую границу массива(теряется гибкость очереди)	O (1)	O (m)

Таблица 1 - Временная оценка различных реализаций очередей

Где n – размер очереди, m размер очереди, которую добавляем в конец к исходной

Таким образом реализовать очередь, которая будет работать за константное время не составляет труда. Вопрос реализации очереди с приоритетом является, бесспорно, более сложной задачей, основные подходы к решению которой мы сейчас рассмотрим

2.2 Основные подходы к реализации очередей с приоритетом

Вопрос реализации очереди с приоритетом стоит сложнее: если для очереди необходимо добавлять в конец, и удалять из начала, то в очереди с приоритетом добавлять и удалять необходимо из произвольной позиции, что в случае с массивом или списком потребует перебора.

Определим требуемые операции:

1) Вставка элемента

2) Извлечение самого приоритетного элемента

3) Получение значения самого приоритетного элемента

4) Изменение ключа элемента

5) Слияние очередей

Очереди с приоритетом можно реализовать при помощи массивов или списковых структур. Среди последних выбирают как связные списки, так и линейные абстрактный типы данных. Однако эти структуры данных не позволяют построить очереди с приоритетом, в которой все операции выполнялись бы быстрее, чем O(n). В тоже время такая реализация необходима при работе с большими объёмами данных. В таких случаях применяют структуры данных, отличные от линейных, например, основанные на сбалансированных деревьях, из которых особо известны бинарные кучи, биномиальные кучи, кучи Фибоначчи.

Куча —структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами)