Ответ
Очередь с приоритетом — это абстрактный тип данных, в котором каждый элемент имеет "приоритет". Элементы извлекаются не в порядке поступления (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), которая обеспечивает эффективность основных операций.
Ответ 18+ 🔞
Вот, слушай, объясняю на пальцах, что это за зверь такой — очередь с приоритетом. Представь себе обычную очередь в кассу, но тут подходит какой-то хитрая жопа с грудой купонов и его сразу пропускают вперёд, потому что у него «приоритет». Вот и вся суть. Не по принципу «кто первый пришёл — тот первый ушёл», а по принципу «у кого цифра в бирочке круче — тот и рулит». Ёпта, как в поликлинике, но только без бабулек.
Основные плюшки и сколько они отжирают времени (если делать на двоичной куче, а не на коленке):
insert(element, priority)/enqueue()— запихнуть элемент: O(log n). Не мгновенно, но и не овердохуища.extractMax()/dequeue()— выдернуть самый важный элемент: O(log n). Примерно та же история.peek()— просто посмотреть, какой там главный по тарелочкам висит: O(1). Мгновенно, потому что он всегда на виду, на самом верху кучи.
Как это выглядит в коде на Java (чтоб не изобретать велосипед, возьмём готовый PriorityQueue):
import java.util.PriorityQueue;
// Создаём очередь. По умолчанию она выдёргивает наименьший элемент первым (то есть, чем МЕНЬШЕ число, тем ВЫШЕ приоритет).
PriorityQueue<Task> taskQueue = new PriorityQueue<>();
// Допустим, у нас есть задачи. Чтобы очередь понимала, как их сравнивать, класс должен реализовать Comparable.
class Task implements Comparable<Task> {
String name;
int priority; // Чем меньше цифра, тем срочнее задача. 1 — это прям «пиздец горит».
@Override
public int compareTo(Task other) {
// Сравниваем по полю priority.
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(); // Метод poll() — выдерни и удали верхушку.
System.out.println(nextTask.name); // Напечатает: "Критичный баг", потом "Рефакторинг", потом "Новая фича".
}Где эта штука в жизни пригождается? Да везде, блядь:
- Планировщик в операционке — решает, какому процессу дать процессорное время.
- Алгоритм Дейкстры для поиска кратчайшего пути — там без неё вообще никуда.
- Разные системы реального времени, где события прилетают пачками и их надо обрабатывать по срочности.
- Слияние кучки отсортированных списков — тоже элегантно решается через такую очередь, ядрёна вошь.
А под капотом-то что? В 99% случаев там двоичная куча (binary heap). Это такое хитрое древовидное представление в обычном массиве, которое и даёт эти логарифмические сложности. Не идеально, но чертовски эффективно для большинства задач. Если, конечно, не пытаться запихнуть туда овердохуища элементов — но это уже совсем другая история.
