Очередь с приоритетом
Очереди с приоритетом — разновидность очередей, в которой у каждого элемента есть свой приоритет. Обслуживаются они в соответствии со своими приоритетом. Если у элементов одинаковый приоритет, то обслуживаются они по их порядку в очереди.
Значение элемента, как правило, и определяет его приоритет.
То есть, у элемента с самым большим значением самый высокий приоритет. Правда, это не всегда так. Самый высокий приоритет может быть у элемента и с самым малым значением. В остальных случаях мы можем задавать приоритеты элементам по своему усмотрению.
Разница между очередью с приоритетом и обычной очередью
Обычная очередь подчиняется принципу FIFO «первый вошел — первый вышел». В очередях с приоритетом элементы удаляются в соответствии с их приоритетом. То есть, элемент с самым высоким приоритетом удаляется из очереди в первую очередь.
Реализация очереди с приоритетом
Очереди с приоритетом можно реализовать с помощью следующих структур данных: массив, связный список, куча и двоичное дерево поиска. Среди всех этих структур выделяется куча — это самый эффективный способ реализации очереди с приоритетом.мы
Именно поэтому в этом руководстве мы будем использовать кучи. Конкретно — max-кучи.
Ниже представлена сравнительная характеристика различных реализаций очередей с приоритетом.