Очередь с приоритетом — структура данных, в которой элементы извлекаются не
по порядку добавления, а по приоритету.
Главное правило:
сначала извлекается элемент с самым важным приоритетом
Обычная очередь работает по FIFO:
первым пришёл -> первым вышел
Очередь с приоритетом работает иначе:
самый высокий приоритет -> первым вышел
Пример:
push("обычная задача", priority = 5)
push("срочная задача", priority = 1)
push("фоновая задача", priority = 10)
Если меньшее число означает более высокий приоритет, порядок извлечения будет:
"срочная задача"
"обычная задача"
"фоновая задача"
Термины
priority queue -> очередь с приоритетом
priority -> приоритет элемента
push(x, priority) -> добавить элемент с приоритетом
pop() -> удалить и вернуть элемент с лучшим приоритетом
peek() -> посмотреть элемент с лучшим приоритетом без удаления
isEmpty() -> проверить, пуста ли очередь
size -> количество элементов
min-priority queue -> первым выходит элемент с минимальным приоритетом
max-priority queue -> первым выходит элемент с максимальным приоритетом
Очередь с приоритетом задаётся четырьмя вещами:
1. набор элементов
2. приоритет каждого элемента
3. правило сравнения приоритетов
4. элемент, который должен выйти следующим
Структура очереди с приоритетом
Структура отвечает на вопрос:
Какой элемент сейчас самый важный?
Внутренний порядок хранения может отличаться от порядка добавления:
добавлены:
(5, "обычная задача")
(1, "срочная задача")
(10, "фоновая задача")
Логический порядок извлечения:
(1, "срочная задача")
(5, "обычная задача")
(10, "фоновая задача")
Важно: очередь с приоритетом обычно не сортирует все элементы полностью.
Её главная задача:
быстро найти и извлечь следующий элемент с лучшим приоритетом
Свойства
Короткая карта свойств очереди с приоритетом:
приоритеты -> у каждого элемента есть значение для сравнения
лучший элемент -> элемент с минимальным или максимальным приоритетом
не FIFO -> порядок добавления не является главным правилом
размер -> количество элементов в очереди
пустота -> очередь может не содержать элементов
сравнение -> нужно уметь сравнивать приоритеты
Конкретная очередь с приоритетом содержит конечное число элементов:
size = n
пустая очередь = size == 0
непустая очередь = size > 0
Для непустой очереди можно определить следующий элемент:
top(priorityQueue)
Важно отделять свойства структуры от характеристик конкретной очереди:
свойство: очередь с приоритетом извлекает лучший элемент
характеристика: лучший элемент сейчас = "срочная задача"
свойство: у элементов есть приоритеты
характеристика: приоритет "срочной задачи" = 1
Min Priority Queue
В min-priority queue первым извлекается элемент с минимальным приоритетом.
priority: 1, 5, 10
pop() -> priority 1
Так работает heapq в Python.
Max Priority Queue
В max-priority queue первым извлекается элемент с максимальным приоритетом.
priority: 1, 5, 10
pop() -> priority 10
Если доступна только min-heap реализация, max-priority queue часто делают через
отрицательные приоритеты:
priority = 10 -> stored priority = -10
priority = 5 -> stored priority = -5
Тогда минимальное сохранённое значение соответствует максимальному исходному
приоритету.
Одинаковые приоритеты
Если у нескольких элементов одинаковый приоритет, нужно явно понимать правило
разрешения ничьей.
Возможные варианты:
по порядку добавления
по дополнительному ключу
по произвольному внутреннему порядку реализации
На практике часто добавляют счётчик:
(priority, insertionOrder, value)
Тогда элементы с одинаковым приоритетом извлекаются в порядке добавления.
Базовые операции
Создание
priorityQueue = []
Обычно:
O(1)
Push
Добавить элемент с приоритетом:
push(priorityQueue, x, priority)
Пример:
push("A", 5)
push("B", 1)
push("C", 10)
Если структура реализована через бинарную кучу:
O(log n)
Pop
Удалить и вернуть элемент с лучшим приоритетом:
pop(priorityQueue)
Пример для min-priority queue:
priorityQueue = [(1, "B"), (5, "A"), (10, "C")]
pop() -> "B"
Условие:
size(priorityQueue) > 0
Если структура реализована через бинарную кучу:
O(log n)
Peek / Top
Посмотреть элемент с лучшим приоритетом без удаления:
peek(priorityQueue)
top(priorityQueue)
Пример:
priorityQueue = [(1, "B"), (5, "A"), (10, "C")]
peek() -> "B"
Условие:
size(priorityQueue) > 0
Если структура реализована через бинарную кучу:
O(1)
Is Empty
Проверить, пуста ли очередь:
isEmpty(priorityQueue)
Пример:
[] -> true
[(1, "B")] -> false
Сложность:
O(1)
Size
Получить количество элементов:
size(priorityQueue)
Обычно:
O(1)
если размер хранится отдельно.
Таблица сложностей
Для реализации через бинарную кучу:
| Операция | Сложность |
|---|---|
| создание | O(1) |
push(x, priority) |
O(log n) |
pop() |
O(log n) |
peek() / top() |
O(1) |
isEmpty() |
O(1) |
size() |
O(1) |
| построение из массива | O(n) |
| поиск произвольного значения | O(n) |
Реализация
Очередь с приоритетом — это абстрактная структура данных. Её можно реализовать
разными способами.
Через бинарную кучу
Самая частая реализация — бинарная куча.
Для min-heap корень содержит минимальный элемент:
1
/ \
3 5
/ \
7 9
В массиве та же куча хранится так:
heap = [1, 3, 5, 7, 9]
Главная идея:
лучший элемент всегда находится в корне
Поэтому:
peek() -> O(1)
push() -> O(log n), потому что нужно восстановить свойство кучи
pop() -> O(log n), потому что нужно восстановить свойство кучи
Через отсортированный массив
Можно хранить элементы отсортированными по приоритету:
[(1, "B"), (5, "A"), (10, "C")]
Тогда:
peek() -> O(1)
pop() -> O(1), если удаляем с удобного конца
push() -> O(n), потому что нужно найти место и сдвинуть элементы
Через неотсортированный массив
Можно просто добавлять элементы в конец:
push() -> O(1)
Но при извлечении нужно искать лучший приоритет:
pop() -> O(n)
peek() -> O(n)
Такой вариант прост, но плохо подходит для частых извлечений.
Очередь, дек и очередь с приоритетом
Обычная очередь:
queue -> первым выходит первый добавленный элемент
Дек:
deque -> можно добавлять и удалять с обоих концов
Очередь с приоритетом:
priority queue -> первым выходит элемент с лучшим приоритетом
Пример различия:
добавили: A(priority=5), B(priority=1), C(priority=10)
queue -> A, B, C
priority queue -> B, A, C
Python
В Python очередь с приоритетом часто реализуют через:
heapq
heapq реализует min-heap: первым извлекается элемент с минимальным значением.
Пример:
import heapq
pq = []
heapq.heappush(pq, (5, "обычная задача"))
heapq.heappush(pq, (1, "срочная задача"))
heapq.heappush(pq, (10, "фоновая задача"))
print(heapq.heappop(pq)) # (1, "срочная задача")
print(heapq.heappop(pq)) # (5, "обычная задача")
print(heapq.heappop(pq)) # (10, "фоновая задача")
Для max-priority queue можно хранить отрицательный приоритет:
import heapq
pq = []
heapq.heappush(pq, (-10, "важная задача"))
heapq.heappush(pq, (-3, "обычная задача"))
priority, value = heapq.heappop(pq)
print(-priority, value) # 10 важная задача
Если приоритеты могут совпадать, удобно добавлять счётчик:
import heapq
pq = []
counter = 0
def push(priority, value):
global counter
heapq.heappush(pq, (priority, counter, value))
counter += 1
push(1, "A")
push(1, "B")
print(heapq.heappop(pq)) # (1, 0, "A")
print(heapq.heappop(pq)) # (1, 1, "B")
Для потокобезопасной очереди с приоритетом есть:
queue.PriorityQueue
Она полезна в многопоточных задачах, но в алгоритмических задачах чаще
используют heapq.
Типичные применения
Dijkstra
A*
Prim
top K elements
merge K sorted lists
медиана потока чисел
планировщик задач
симуляции событий
выбор следующей самой выгодной операции
Формальная схема
PriorityQueue = {
elements: e1, e2, ..., en,
priority: priority(ei),
comparator: правило сравнения приоритетов,
top: элемент с лучшим приоритетом,
size: n
}
Операции очереди с приоритетом изменяют или используют одну из четырёх
сущностей:
приоритет
лучший элемент
размер
правило сравнения
Примеры:
push(x, priority) -> добавляет элемент и восстанавливает порядок приоритетов
pop() -> возвращает лучший элемент и восстанавливает структуру
peek() -> читает лучший элемент без удаления
isEmpty() -> проверяет размер
Минимальная формулировка:
очередь с приоритетом = структура для быстрого извлечения самого важного элемента
