Priority Queue | kz-maxx

Түсіндіру

Priority Queue, яғни очередь с приоритетом — бұл структура данных. Мұнда бірінші болып ерте келген элемент емес, приоритеті жоғары элемент шығады.

обычная очередь:
кім бірінші келді → сол бірінші шығады

priority queue:
кімнің priority жоғары → сол бірінші шығады

C++ ішінде дайын структура бар:

priority_queue<int> q;

Ішінде priority_queue көбіне binary heap арқылы жұмыс істейді. Яғни бұл дайын куча сияқты.

C++ ішінде priority_queue по умолчанию max-heap. Яғни ең үлкен элемент жоғарыда тұрады.

Негізгі операциялар

Операция	Не істейді	Уақыт
push(x)	x элементін қосады	O(log n)
top()	ең жоғары priority бар элементті қайтарады	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

Командаларды орындау керек. Біз 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

Кейбір есептерде бір ғана сан емес, екі мән сақтау керек болады. Мысалы:

{priority, vertex}
{distance, vertex}
{score, id}

Ол үшін pair қолданамыз:

priority_queue<pair<int, int>> q;

Pair қалай салыстырылады?

бірінші 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

pair-лар: {5, 1}, {10, 2}, {7, 3}
ең үлкен first = 10
top = {10, 2}

Min-heap үшін pair

Егер ең кіші 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 бойынша алу

Бізде бірнеше задача бар. Әр задачада:

priority — важность
id — задачаның нөмірі

Әрқашан priority ең үлкен задачаны алу керек.

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}

Өзіміздің sorting rule

Кейде өзіміздің салыстыру ережесін жазу керек болады. Ол үшін cmp структурасын жазамыз.

Мысалы, time ең кіші задача жоғарыда тұрсын.

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 ең кіші Task жоғарыда болады.

Толық кішкентай мысал

#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 қайда қолданылады?

Дейкстра алгоритмі
Жадные алгоритмы
Расписание есептері
Event simulation
k ең үлкен немесе k ең кіші элемент табу

Егер есепте әрқашан тез minimum немесе maximum алу керек болса, priority_queue туралы ойлануға болады.

Асимптотика

Операция	Уақыт
push	O(log n)
pop	O(log n)
top	O(1)
size	O(1)
empty	O(1)