Modul 1: 2D DP

Eng uzun umumiy quyi-ketma-ketlik (LCS)
Eng uzun o‘suvchi qism ketma-ketlik
$O(N \log N)$ uchun eng uzun o‘suvchi qism ketma-ketlik (LIS)
Ryukzak masalasi
Lazy DP

Modul 2: DSU

DSU - Kesishmaydigan to‘plamlar tizimi

Modul 3: MST

Minimal va maksimal qamrovchi daraxtlar
Kruskal algoritmi
Prima algoritmi
Boruvka algoritmi

Modul 4: Kombinatorika

Yulduzlar va ustunlar
Qo‘shish-ayirish prinsipi

Modul 5: Geometriya

Finding the area of a simple polygon

Modul 6: Uzun sonli arifmetika

Uzun arifmetika

Modul 7: Minimum saqlash uchun strukturalar

Minimumli stek
Minimumli navbat
Minimumli deque

Modul 8: Heap [BONUS]

Heap

Heap - Course 3

Bosh sahifa Kurslar Resurslar Masalalar Milliy olimpiada Musobaqalar Reyting

...

Bosh sahifa/Courses/Course 3/Modul 8: Heap [BONUS]/Heap

Heap

Heap (Ikkilik uyma)

Ikkilik uyum (Binary Heap)

Kirish

Ikkilik uyum (binary heap) — bu shunday ikkilik osilgan daraxtki, u uchun quyidagi shartlar bajariladi:

Har bir cho‘qqining ikkitadan ortiq farzandi yo‘q.
Istalgan cho‘qqining qiymati uning farzandlaridagi qiymatlardan kam emas (bu max-heap).

Shuningdek, uyum deyarli to‘liq ikkilik daraxt hisoblanadi:

$i$ -chi (noldan boshlab) qatlamda $2^i$ ta cho‘qqi bo‘ladi, oxirgisidan tashqari.
Oxirgi qatlam chapdan o‘ngga to‘ldiriladi.

Tuzilma

Uyumni $a_0, a_1, \ldots, a_{n-1}$ massivida saqlash qulay.

,

a1

,

…

,

an−1

Ildiz: $a_0$
$a_i$ $a_{i}$ cho‘qqining farzandlari:
- chap: $a_{2i+1}$
- o‘ng: $a_{2i+2}$

Uyum balandligi $O(\log N)$ ga teng, shuning uchun asosiy amallar tez bajariladi.

Ikki asosiy protsedura

Biz doimo uyum xossasini saqlaymiz, bunda har bir ota-ona $\geq$ o‘z farzandlaridan. Shu tufayli maksimum har doim ildizda bo‘ladi.

`sift_up(i)` — yuqoriga ko‘tarish

push da ishlatiladi.

Algoritm:

Elementni massiv oxiriga qo‘shamiz.
Element o‘z ota-onasidan katta bo‘lsa:
- ularni joyini almashtiramiz
- ota-onaga ko‘tarilamiz

Uyum balandligi $O(\log N)$ bo‘lgani uchun, amal $O(\log N)$ da ishlaydi.

`sift_down(i)` — pastga elash

pop da ishlatiladi.

Algoritm:

Ildizni oxirgi element bilan almashtiramiz.
Oxirgi elementni o‘chiramiz.
Yangi ildizni pastga elaymiz:
- kattaroq farzandni tanlaymiz
- agar farzand ota-onadan katta bo‘lsa — ularni joyini almashtiramiz
- jarayonni davom ettiramiz

Shuningdek $O(\log N)$ da ishlaydi.

Realizatsiya

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();
    }
};