04 — Куча (Heap min/max) и приоритетные очереди

Куча (структура данных)

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

Кучи также можно представить в виде массива таким образом, что:

Если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами.

Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи. На практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом.

Узел на вершине кучи, у которого нет родителей, называется корневым узлом.

Очередь с приоритетом

Очередь с приоритетом (англ. priority queue) — абстрактный тип данных в информатике, для каждого элемента которого можно вычислить его приоритет.

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

Очередь с приоритетом поддерживает две обязательные операции — добавить элемент и извлечь максимум(минимум).

Хотя приоритетные очереди часто реализуются в виде куч(heaps), они концептуально отличаются от куч. Очередь приоритетов является абстрактной концепцией вроде «списка» или «карты»; так же, как список может быть реализован в виде связного списка или массива, так и очередь с приоритетом может быть реализована в виде кучи или множеством других методов, например в виде неупорядоченного массива.