Объяснение

Куча — это структура данных, которая быстро находит самый маленький или самый большой элемент.

Есть два основных вида кучи:

• min-heap — сверху всегда минимальный элемент
• max-heap — сверху всегда максимальный элемент

Куча похожа на бинарное дерево, но хранится в обычном массиве.

Как куча хранится в массиве?

Используем массив:

int h[N];
int sz;

• h — массив кучи
• sz — количество элементов в куче

Индексация начинается с 1. Это удобно, потому что легко находить родителей и детей.

Пример

Это дерево можно представить так:

Для 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 нужен после добавления нового элемента. Мы добавляем элемент в конец массива. Если он меньше родителя, поднимаем его выше.

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

Новый элемент 1 стоит на позиции 4. Его родитель — позиция 2, там стоит 5. Так как 1 < 5, меняем их местами.

Теперь 1 стоит на позиции 2. Его родитель — позиция 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].

Чтобы удалить его:

• ставим последний элемент на место первого
• уменьшаем размер
• вызываем 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, потому что это минимальный элемент.

Асимптотика