Эта статья будет основываться на моей предыдущей статье о кучах. Напомним, что куча — это особый вид двоичного дерева, которое следует набору правил. Куча может быть максимальной кучей, которая будет иметь наибольшее значение в качестве корня, а значение каждого родительского узла всегда больше, чем его дочерние узлы. В противном случае это минимальная куча, которая будет иметь наименьшее значение в качестве корня, а значение каждого родительского узла всегда меньше, чем его дочерние узлы. Кучи не имеют подразумеваемого порядка между братьями и сестрами.
Очередь с приоритетами — одна из самых полезных реализаций кучи. Очередь с приоритетом — это структура данных, в которой каждый элемент имеет приоритет и значение. Как и в случае с кучами, существует два вида очередей с приоритетом: очередь с максимальным приоритетом и очередь с минимальным приоритетом. Для очереди с максимальным приоритетом элементы с более высоким приоритетом обслуживаются раньше элементов с более низким приоритетом. И наоборот для очереди с минимальным приоритетом.
Типичным примером очереди с приоритетом в реальной жизни может быть очередь в больнице, где пациент с наиболее критической ситуацией будет первым в очереди. При этом приоритетным является положение каждого больного.
Реализации
Очереди с приоритетом могут быть реализованы с использованием общей структуры данных, такой как массивы, связанные списки, кучи и двоичные деревья. Очереди с приоритетом связаны с кучами, поскольку кучи обеспечивают эффективную реализацию очередей с приоритетом.
Операции и Большой О
Peek — возвращает максимальный элемент из очереди с максимальным приоритетом или минимальный элемент из очереди с минимальным приоритетом без удаления узла. Занимает постоянное время O(1).
Вставить — добавить элемент в приоритетную очередь. Подобно разделу «Вставка» в моей статье Heaps. Занимает логарифмическое время O(log n), так как новый элемент приоритета должен быть назначен, и высота кучи перенастраивается.
Удалить — удаляет самый большой элемент из очереди с максимальным приоритетом или удаляет самый маленький элемент из очереди с минимальным приоритетом. Подобно разделу «Удаление самого большого элемента» в моей статье Heaps. Занимает логарифмическое время O(log n), так как новый элемент приоритета должен быть назначен, таким образом корректируя высоту кучи.
Приложения
Алгоритм кратчайшего пути Дейкстры с использованием очереди приоритетов: может эффективно извлекать минимум из графа, который хранится в виде списка смежности или матрицы при реализации алгоритма Дейкстры.
Алгоритм Прима: хранить ключи узлов и извлекать минимальный ключевой узел на каждом шаге.
Коды Хаффмана: используются для сжатия данных.
A* Алгоритм поиска: используется для отслеживания неизведанных маршрутов, для которого высший приоритет отдается тому, у которого нижняя граница общей длины пути наименьшая. Алгоритм поиска A* находит кратчайший путь между двумя вершинами взвешенного графа, сначала пробуя наиболее перспективные маршруты.
Heap Sort: типичная реализация Priority Queue.
Ресурсы
Для получения дополнительных ресурсов по приоритетным очередям я предлагаю просмотреть эти полезные ссылки.
Моя куча статьи: https://chandler-hanson.medium.com/heap-heap-heap-d423320a4997
https://datastructures.maximal.io/priority-queues/
https://www.geeksforgeeks.org/implementation-priority-queue-javascript/
https://medium.com/@angeloacebedo/an-intro-to-priority-queues-a28c2e09db70
https://medium.com/basecs/learning-to-love-heaps-cef2b273a238
https://www.hackerearth.com/practice/notes/heaps-and-priority-queues/
