Түсіндіру

Heap, яғни куча — бұл структура данных. Ол ең кіші немесе ең үлкен элементті тез табуға көмектеседі.

Кучаның екі негізгі түрі бар:

• min-heap — ең кіші элемент жоғарыда тұрады
• max-heap — ең үлкен элемент жоғарыда тұрады

Куча binary tree сияқты көрінеді, бірақ кодта ол жай массивте сақталады.

Куча массивте қалай сақталады?

Біз екі айнымалы қолданамыз:

int h[N];
int sz;

• h — куча сақталатын массив
• sz — кучада қанша элемент бар

Индексация 1-ден басталады. Себебі онда parent және child табу оңай болады.

Мысал

Бұл кучаны дерево сияқты былай елестетуге болады:

Min-heap үшін правило:

Мысалы, 2 өзінің балалары 5 және 7-ден кіші. Сондықтан ең кіші элемент жоғарыда тұр.

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

Есеп мысалы

Min-heap үшін бірнеше команда орындау керек.

Input

8
push 5
push 2
push 7
top
pop
top
push 1
top

Output

2
5
1

Толық реализация

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

const int N = 100010;

int h[N];
int sz;

void up(int u) {
    while (u / 2 > 0 && h[u] < h[u / 2]) {
        swap(h[u], h[u / 2]);
        u /= 2;
    }
}

void down(int u) {
    int t = u;

    if (u * 2 <= sz && h[u * 2] < h[t]) {
        t = u * 2;
    }

    if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) {
        t = u * 2 + 1;
    }

    if (t != u) {
        swap(h[u], h[t]);
        down(t);
    }
}

void push(int x) {
    sz++;
    h[sz] = x;
    up(sz);
}

int top() {
    return h[1];
}

void pop() {
    h[1] = h[sz];
    sz--;
    down(1);
}

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

    int q;
    cin >> q;

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

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

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

    return 0;
}

Функциялар түсіндірмесі

1. up

void up(int u) {
    while (u / 2 > 0 && h[u] < h[u / 2]) {
        swap(h[u], h[u / 2]);
        u /= 2;
    }
}

up жаңа элемент қосылғаннан кейін керек. Жаңа элемент алдымен массивтің соңына қосылады. Егер ол parent-тен кіші болса, жоғары көтеріледі.

Кішкентай мысал

Жаңа элемент 1 позиция 4-те тұр. Оның parent-і позиция 2, онда 5 тұр. 1 < 5, сондықтан орындарын ауыстырамыз.

Енді 1 позиция 2-де тұр. Оның parent-і позиция 1, онда 2 тұр. 1 < 2, тағы ауыстырамыз.

Енді 1 жоғарыда тұр. Куча дұрыс болды.

2. down

void down(int u) {
    int t = u;

    if (u * 2 <= sz && h[u * 2] < h[t]) {
        t = u * 2;
    }

    if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) {
        t = u * 2 + 1;
    }

    if (t != u) {
        swap(h[u], h[t]);
        down(t);
    }
}

down ең жоғарғы элемент өшірілгеннен кейін керек. Біз соңғы элементті жоғарыға қоямыз. Кейін ол өз орнын тапқанша төмен түседі.

Кішкентай мысал

1 өшіріледі. Соңғы элемент 5 жоғарыға қойылады.

5-тің балалары 3 және 2. Ең кіші бала — 2. 2 < 5, сондықтан ауыстырамыз.

Куча қайтадан дұрыс болды.

3. push

void push(int x) {
    sz++;
    h[sz] = x;
    up(sz);
}

push жаңа элементті соңына қосады. Кейін up шақырып, оны дұрыс орынға көтереді.

4. top

int top() {
    return h[1];
}

Min-heap-та ең кіші элемент әрқашан h[1]-де тұрады. Сондықтан top жай ғана h[1] қайтарады.

5. pop

void pop() {
    h[1] = h[sz];
    sz--;
    down(1);
}

pop ең кіші элементті өшіреді. Ал ең кіші элемент h[1]-де тұрады.

Өшіру жолы:

• соңғы элементті бірінші орынға қоямыз
• sz мәнін азайтамыз
• down(1) шақырамыз

priority_queue в C++

C++ ішінде дайын куча бар — priority_queue. По умолчанию ол max-heap болып жұмыс істейді.

Max-heap

priority_queue<int> q;

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

cout << q.top();

Мұнда top() 7 қайтарады, себебі ол ең үлкен элемент.

Min-heap

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

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

cout << q.top();

Мұнда top() 2 қайтарады, себебі ол ең кіші элемент.

Асимптотика