Структура Данных Куча и Очередь с Приоритетом в .NET. Начало
В .NET термин «куча» обычно используется при обсуждении управления памятью. Но сегодня мы рассмотрим, что такое структура данных куча, чем она полезна и как используется в типе PriorityQueue в .NET.
Куча — это структура данных, которая обычно представляется в виде дерева и удовлетворяет следующим правилам:
- Минимальная куча — для каждого узла в дереве значение узла меньше (или равно) значений его дочерних элементов.
- Максимальная куча — для каждого узла в дереве значение узла больше (или равно) значений его дочерних элементов.
На рисунке ниже показана визуализация минимальной кучи, включая некоторые термины. Куча на рисунке - двоичная, (каждый узел имеет до два дочерних). Также говорят, что арность кучи 2.
Обычно отношения описываются так, как если бы куча представляла собой генеалогическое древо:
- корневой узел — узел наверху кучи. В минимальной куче корневой узел имеет наименьшее значение.
- братья — узлы, имеющие общего родителя.
- кузены — узлы, имеющие общего предка.
На рисунке ниже видно, что для каждого узла родительское значение меньше (или равно) дочернему. Однако между братьями нет никакой связи (кроме того, что они больше родителя). Так же, кузены не связаны между собой, но гарантированно больше, чем их общий предок (в минимальной куче). Обратите внимание, что это отличается от двоичного дерева поиска, в котором существуют отношения между братьями.
Кучи обычно реализуются как массивы, в которых каждый элемент представляет узел кучи. Позиция определяет связь между узлами, как показано на рисунке ниже. Здесь:
- Элемент с индексом 0 - корневой. В минимальной куче это минимальное значение в куче.
- Элементы 1 и 2 - дочерние корневого.
- 3 и 4 - дочерние элемента 1, 5 и 6 — дочерние элемента 2 и т. д.
Основное использование кучи — реализация очереди с приоритетом. «Обычная» очередь хранит элементы так же, как очередь в магазине: вы добавляете элементы в очередь на одном конце, и удаляете элементы из очереди с другого конца. Очередь с приоритетом представляет собой разновидность стандартной очереди. Вы по-прежнему можете ставить элементы в очередь и удалять их из очереди, но вместо того, чтобы возвращать элементы в том порядке, в котором вы их добавили, вы всегда возвращаете наименьший из оставшихся элементов.
В качестве примера рассмотрим тип PriorityQueue, появившийся в .NET 6:
// добавляем элементы с разным приоритетом
var q = new PriorityQueue<string, int>([
("A", 15), ("B", 7), ("C", 23), ("D", 2), ("E", 22)
]);
// выбираем элементы в порядке приоритета
while (q.TryDequeue(out var elem, out var priority))
Console.WriteLine($"{elem}: {priority}");
// Вывод
// D: 2
// B: 7
// A: 15
// E: 22
// C: 23
Элементы извлекаются в порядке возрастания приоритета. Куча —распространённый (но не единственный) способ реализации очереди с приоритетом. Очередь с приоритетом имеет множество применений. Одно из наиболее известных — графовые алгоритмы, таких как алгоритм Дейкстры, для определения наименьшего расстояния между двумя узлами.
Окончание следует…
Источник: https://andrewlock.net/an-introduction-to-the-heap-data-structure-and-dotnets-priority-queue/