Что такое очередь с приоритетом (Priority Queue)?

Очередь с приоритетом — это абстрактный тип данных, в котором каждый элемент имеет "приоритет". Элементы извлекаются не в порядке поступления (FIFO), а в порядке убывания (или возрастания) приоритета.

Ключевые операции и их сложность (на основе двоичной кучи):

• insert(element, priority) / enqueue(): O(log n)
• extractMax() / extractMin() / dequeue(): O(log n)
• peek() (посмотреть элемент с наивысшим приоритетом): O(1)

Реализация и пример на Java (используя PriorityQueue):

import java.util.PriorityQueue;

// Очередь с приоритетом по умолчанию (наименьший элемент - высший приоритет)
PriorityQueue<Task> taskQueue = new PriorityQueue<>();

// Предположим, класс Task реализует Comparable или мы передали Comparator
class Task implements Comparable<Task> {
    String name;
    int priority; // чем меньше число, тем выше приоритет

    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}

// Добавление задач
taskQueue.add(new Task("Критичный баг", 1));
taskQueue.add(new Task("Новая фича", 3));
taskQueue.add(new Task("Рефакторинг", 2));

// Извлечение в порядке приоритета
while (!taskQueue.isEmpty()) {
    Task nextTask = taskQueue.poll(); // Извлекает и удаляет голову очереди
    System.out.println(nextTask.name); // Выведет: Критичный баг, Рефакторинг, Новая фича
}

Типичные сценарии использования:

• Планировщик задач в ОС.
• Алгоритм Дейкстры для поиска кратчайшего пути в графе.
• Обработка событий в системах реального времени.
• Слияние K отсортированных списков (используя кучу минимальных элементов).

Реализация "под капотом" чаще всего основана на двоичной куче (binary heap), которая обеспечивает эффективность основных операций.