Представим что нужно спроектировать список задач. У каждой задачи есть приоритет, это значит, что вначале должны быть самые приоритетные задачи. Сами задачи можно обрабатывать только по одной, мы не можем взять задачу с центра списка.

Такой список достаточно просто реализовать с помощью обычного массива. Задачи будем хранить в случайном порядке, а в момент получения текущей задачи будем искать самую приоритетную. В таком случае добавление новой задачи будет иметь сложность O(1), а вот получение O(n), потому что каждый раз нужно искать элемент с самым большим приоритетом.

Второй вариант тоже использует обычный массив, только элементы в нем хранятся уже в отсортированном виде. В таком случае сложность меняется зеркально. Добавление нового элемента будет занимать O(n), а получение O(1).

Оба варианта не совсем эффективны, особенно когда очень много данных. Здесь на помощь приходят очереди с приоритетом.

Очереди с приоритетом строятся на базе такой структуры данных как куча. Поэтому важно рассмотреть ее устройство. Куч есть большое множество, но нас сейчас интересует только двоичная куча.

Двоичная куча

Двоичная куча представляет из себя двоичное дерево где каждый элемент имеет два дочерних элемента и хранит значение не меньшее чем в дочерних. Они также делятся на два типа: максимальная и минимальная. В первой хранятся элементы в порядке убывания, а во второй в порядке возрастания.

Для хранения данных кучи удобно использовать обычные массивы. Такой подход занимает мало места и сам по себе достаточно элегантный. На как определить какой элемент массива на какой ссылается? Для этого есть две простые формулы.

• 2i + 1 — позволяет найти позицию левого дочернего элемента
• 2i + 2 — позволяет найти позицию правого дочернего элемента

Сортировка дерева

Когда добавляем или удаляем элемент из очереди, свойства кучи могут нарушиться. В таком случае нужно привести ее в порядок. Представим, что есть метод MakeHeap, который принимает на вход индекс элемента и он сортирует его поддерево.

Берем элемент по текущему индексу и сравниваем его с дочерними элементами. Если какой-то дочерний элемент больше текущего, меняем его местами с текущим и спускаемся дальше, чтобы проверить поддерево. Таким образом, мы доходим до конца изначального поддерева сортируя все его поддеревья.

Как это выглядит в коде:

private void SortHeap(int i)
{
	var size = values.Count;
	var left = 2 * i + 1;
	var right = 2 * i + 2;
	var largest = i;
	
	if (left < size && values[left] > values[largest])
		largest = left;
		
	if (right < size && values[right] > values[largest])
		largest = right;
		
	if (largest != i)
	{
		var temp = values[i];
		values[i] = values[largest];
		values[largest] = temp;
		SortHeap(largest);
	}
}

Делаем кучу из обычного массива

Мы умеем сортировать элементы в поддеревьях, теперь применим этот метод для того, чтобы с обычного массива сделать кучу. Так как потомки гарантированно есть у первых (n/2 — 1) элементов, то достаточно только для них вызвать метод SortHeap.

private void MakeHeap()
{
	for (int i = values.Count / 2 - 1; i >= 0; i--)
	{
		SortHeap(i);
	}
}

Добавление нового элемента

Новый элемент сначала добавляется в конец массива, после чего запускаем сортировку дерева. Алгоритм получается достаточно простым:

if (values.Count == 0)
{
	// Просто добавляем в элемент в массив, если он пустой
	values.Add(value);
}
else
{
	// Добавляем элемент в конец массива и запускаем сортировку дерева
	values.Add(value);
	for (int i = values.Count / 2 - 1; i >= 0; i--)
	{
		SortHeap(i);
	}		
}

Удаление элемента

Чтобы удалить элемент нужно поменять его с последним элементов в куче, потом удалить и запустить сортировку кучи. Так как мы делаем очередь, то будем всегда удалять первый (корневой) элемент кучи.

var size = values.Count;
		
var last = values.Count - 1;
var temp = values[0];
values[0] = values[last];
values[last] = temp;
values.RemoveAt(last);

for (int i = size / 2 - 1; i >= 0; i--)
	SortHeap(i);

return temp;

Итого

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

• Enqueue — обычная вставка в кучу, ничего даже менять не нужно.
• Dequeue — обычное удаление элемента с кучи, только удаляем мы всегда элемент с 0 индексов.

Посмотреть полную реализацию можно на dotnetfiddle.