Двоичная Куча - Course 3

Module 1: 2D DP

Наибольшая общая подпоследовательность (НОП)
Наибольшая возрастающая подпоследовательность (НВП)
Наибольшая возрастающая подпоследовательность (НВП) за $O(N \log N)$
Задача рюкзака
Lazy DP

Module 2: DSU

Система непересекающихся множеств

Module 3: MST

Минимальные и максимальные остовные деревья
Kruskal's Algorithm
Алгоритм Прима
Алгоритм Борувки

Module 4: Combinatorics

Звезды и столбцы
Принцип включения-исключения

Module 5: Geometry

Нахождение площади простого многоугольника

Module 6: Arbitrary-Precision Arithmetic

Длинная Арифметика

Module 7: Data structures for keeping minimum

Stack with Minimum
Queue with Minimum
Deque with Minimum

Module 8: Heap [BONUS]

Двоичная Куча

Главная Курсы Ресурсы Задачи Национальная олимпиада Соревнования Таблица лидеров

...

Главная/Courses/Course 3/Module 8: Heap [BONUS]/Двоичная Куча

Двоичная Куча

Двоичная Куча

Двоичная куча (Binary Heap)

Введение

Двоичная куча (binary heap) — это двоичное подвешенное дерево, для которого выполняются условия:

У каждой вершины не более двух сыновей.
Значение любой вершины не меньше значений в её сыновьях (это max-heap).

Также куча является почти полным двоичным деревом:

На $i$ -ом (начиная с нуля) слое находится $2^i$ вершин, кроме последнего.
Последний слой заполнен слева направо.

Структура

Кучу удобно хранить в массиве $a_0, a_1, \ldots, a_{n-1}$ .

,

a1

,

…

,

an−1

Корень: $a_0$
Дети вершины $a_i$ $a_{i}$ :
- левый: $a_{2i+1}$
- правый: $a_{2i+2}$

Высота кучи равна $O(\log N)$ , поэтому основные операции выполняются быстро.

Две ключевые процедуры

Мы всегда поддерживаем свойство кучи, где каждый родитель $\geq$ своих детей. Благодаря этому максимум всегда находится в корне.

`sift_up(i)` — поднятие вверх

Используется при push.

Алгоритм:

Вставляем элемент в конец массива.
Пока элемент больше своего родителя:
- меняем их местами
- поднимаемся к родителю

Поскольку высота кучи $O(\log N)$ , операция работает за $O(\log N)$ .

`sift_down(i)` — просеивание вниз

Используется при pop.

Алгоритм:

Меняем корень с последним элементом.
Удаляем последний элемент.
Просеиваем новый корень вниз:
- выбираем большего ребёнка
- если ребёнок больше родителя — меняем их местами
- продолжаем процесс

Также работает за $O(\log N)$ .

Реализация

struct Heap {
    vector<int> a;

    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return 2 * i + 1; }
    int right(int i) { return 2 * i + 2; }

    void sift_up(int i) {
        while (i > 0 && a[parent(i)] < a[i]) {
            swap(a[parent(i)], a[i]);
            i = parent(i);
        }
    }

    void sift_down(int i) {
        while (true) {
            int l = left(i);
            int r = right(i);
            int best = i;

            if (l < (int)a.size() && a[l] > a[best]) {
                best = l;
            }
            if (r < (int)a.size() && a[r] > a[best]) {
                best = r;
            }

            if (best == i) {
                break;
            }

            swap(a[i], a[best]);
            i = best;
        }
    }

    void push(int x) {
        a.push_back(x);
        sift_up((int)a.size() - 1);
    }

    int top() {
        return a[0];
    }

    void pop() {
        a[0] = a.back();
        a.pop_back();
        if (!a.empty()) {
            sift_down(0);
        }
    }

    bool empty() {
        return a.empty();
    }

    int size() {
        return (int)a.size();
    }
};