Очередь с приоритетом

Объяснение

Очередь с приоритетом — это структура данных, где первым выходит не тот, кто раньше зашел, а тот, у кого приоритет выше.

обычная очередь:
кто первый пришел → тот первый вышел

очередь с приоритетом:
у кого приоритет больше → тот первый вышел

В C++ для этого есть готовая структура:

priority_queue<int> q;

Внутри priority_queue обычно работает через binary heap. То есть это удобная готовая куча.

По умолчанию priority_queue в C++ — это max-heap. То есть наверху всегда самый большой элемент.

Главные операции

Операция	Что делает	Время
push(x)	добавляет элемент x	O(log n)
top()	возвращает элемент с самым высоким приоритетом	O(1)
pop()	удаляет верхний элемент	O(log n)
size()	возвращает размер очереди	O(1)
empty()	проверяет, пустая очередь или нет	O(1)

Max-heap

По умолчанию priority_queue<int> работает как max-heap. Самое большое число всегда находится сверху.

priority_queue<int> q;

q.push(5);
q.push(2);
q.push(7);

cout << q.top();

Ответ будет:

добавили: 5, 2, 7
самый большой элемент = 7
q.top() = 7

Маленький пример с pop

priority_queue<int> q;

q.push(5);
q.push(2);
q.push(7);

cout << q.top() << '\n';

q.pop();

cout << q.top() << '\n';

Вывод:

7
5

Сначала наверху было 7. После pop() число 7 удалилось, и наверху стало 5.

Min-heap

Чтобы сверху был самый маленький элемент, нужно написать так:

priority_queue<int, vector<int>, greater<int>> q;

Это уже min-heap.

priority_queue<int, vector<int>, greater<int>> q;

q.push(5);
q.push(2);
q.push(7);

cout << q.top();

Ответ будет:

добавили: 5, 2, 7
самый маленький элемент = 2
q.top() = 2

Если задача просит каждый раз брать минимум, чаще всего нужен min-heap.

Пример задачи 1: обычная очередь с приоритетом

Нужно обработать команды для min-heap.

Команда	Что делает
push x	добавить число x
top	вывести минимальный элемент
pop	удалить минимальный элемент
size	вывести размер очереди

Input

9
push 5
push 2
push 7
top
pop
top
push 1
top
size

Output

Полная реализация min-heap

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    priority_queue<int, vector<int>, greater<int>> q;

    int n;
    cin >> n;

    while (n--) {
        string op;
        cin >> op;

        if (op == "push") {
            int x;
            cin >> x;

            q.push(x);
        } else if (op == "top") {
            cout << q.top() << '\n';
        } else if (op == "pop") {
            q.pop();
        } else if (op == "size") {
            cout << q.size() << '\n';
        }
    }

    return 0;
}

Очередь с приоритетом для pair

Часто в задачах нужно хранить не одно число, а пару. Например:

{приоритет, номер вершины}

Для этого можно использовать:

priority_queue<pair<int, int>> q;

По умолчанию пары сравниваются так:

сначала сравнивается first
если first одинаковые, сравнивается second

Пример max-heap для pair

priority_queue<pair<int, int>> q;

q.push({5, 1});
q.push({10, 2});
q.push({7, 3});

cout << q.top().first << ' ' << q.top().second;

Ответ:

10 2

пары: {5, 1}, {10, 2}, {7, 3}
самый большой first = 10
top = {10, 2}

Min-heap для pair

Чтобы получить минимальную пару, пишем:

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

Пример

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

q.push({5, 1});
q.push({10, 2});
q.push({7, 3});

cout << q.top().first << ' ' << q.top().second;

Ответ:

5 1

Такая запись часто используется в алгоритме Дейкстры: {distance, vertex}.

Пример задачи 2: обработка задач по важности

Пусть есть задачи. У каждой задачи есть:

priority — важность
id — номер задачи

Нужно всегда брать задачу с максимальной важностью.

Input

7
add 10 1
add 5 2
add 20 3
top
pop
top
size

Output

20 3
10 1
2

Реализация с pair

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    priority_queue<pair<int, int>> q;

    int n;
    cin >> n;

    while (n--) {
        string op;
        cin >> op;

        if (op == "add") {
            int priority, id;
            cin >> priority >> id;

            q.push({priority, id});
        } else if (op == "top") {
            cout << q.top().first << ' ' << q.top().second << '\n';
        } else if (op == "pop") {
            q.pop();
        } else if (op == "size") {
            cout << q.size() << '\n';
        }
    }

    return 0;
}

Как это работает?

add 10 1 → задача с priority 10 и id 1
add 5 2 → задача с priority 5 и id 2
add 20 3 → задача с priority 20 и id 3

Так как это max-heap, наверху будет задача с самым большим priority.

top = {20, 3}

Своя сортировка

Иногда нужно задать свои правила сравнения. Тогда можно написать структуру cmp.

Например, хотим, чтобы сверху была задача с меньшим временем.

struct Task {
    int time;
    int id;
};

struct cmp {
    bool operator()(Task a, Task b) {
        return a.time > b.time;
    }
};

priority_queue<Task, vector<Task>, cmp> q;

Здесь сверху будет задача с минимальным time.

Полный маленький пример

#include <bits/stdc++.h>
using namespace std;

struct Task {
    int time;
    int id;
};

struct cmp {
    bool operator()(Task a, Task b) {
        return a.time > b.time;
    }
};

int main() {
    priority_queue<Task, vector<Task>, cmp> q;

    q.push({10, 1});
    q.push({5, 2});
    q.push({20, 3});

    cout << q.top().time << ' ' << q.top().id;

    return 0;
}

Ответ:

5 2

Где используется priority_queue?

Алгоритм Дейкстры
Жадные алгоритмы
Задачи с расписанием
Симуляции событий
Нахождение k самых больших или маленьких элементов

Если в задаче нужно каждый раз быстро брать минимум или максимум, почти всегда можно подумать про priority_queue.

Асимптотика

Операция	Время
push	O(log n)
pop	O(log n)
top	O(1)
size	O(1)
empty	O(1)