Skip to content

🧱 Разширени Хепове (Advanced Heaps)

Стандартната структура "Двоична пирамида" (Binary Heap), използвана в std::priority_queue, е изключително ефективна за операциите push (\(O(\log N)\)) и pop (\(O(\log N)\)). Въпреки това, тя има един съществен недостатък: сливането (merge) на две пирамиди отнема \(O(N)\) време.

В много алгоритми (напр. Minimum Spanning Tree с алгоритъм на Chu-Liu/Edmonds, Dijkstra върху специални графи) се налага ефикасно сливане на опашки. Тук на помощ идват Обединяемите пирамиди (Mergeable Heaps).

1. Лява пирамида (Leftist Heap)

Лявата пирамида е двоично дърво, което спазва две свойства: 1. Heap Property: Стойността във всеки възел е по-малка (или по-голяма, за max-heap) от стойностите на децата му. 2. Leftist Property: За всеки възел, "разстоянието" до най-близкия null наследник в дясното поддърво е по-малко или равно на това в лявото. * Нека \(dist(u)\) е дължината на най-късия път от \(u\) до възел, който няма две деца. * Изискване: \(dist(u \to left) \ge dist(u \to right)\).

Това свойство гарантира, че десният път (Right Spine) на дървото е кратък: дължината му е най-много \(O(\log N)\). Тъй като повечето операции се извършват по десния път, те са логаритмични.

1.1. Операция Сливане (Merge)

Това е основната операция. Всички други (insert, pop) се дефинират чрез нея. За да слеем две пирамиди \(A\) и \(B\): 1. Ако едната е празна, връщаме другата. 2. Нека коренът на \(A\) е по-малък от корена на \(B\) (за min-heap). Ако не, разменяме \(A\) и \(B\). 3. Сливаме дясното дете на \(A\) с \(B\): A->right = merge(A->right, B). 4. След сливането, ако \(dist(A \to left) < dist(A \to right)\), разменяме лявото и дясното дете на \(A\), за да възстановим leftist свойството. 5. Обновяваме \(dist(A) = dist(A \to right) + 1\).

Сложност: \(O(\log N)\).

struct Node {
    int val, dist;
    Node *left, *right;
    Node(int v) : val(v), dist(0), left(nullptr), right(nullptr) {}
};

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->val > b->val) swap(a, b); // Min-heap

    a->right = merge(a->right, b);

    if (!a->left || a->left->dist < a->right->dist) {
        swap(a->left, a->right);
    }

    if (a->right) a->dist = a->right->dist + 1;
    else a->dist = 0;

    return a;
}

2. Skew Heap (Наклонена пирамида)

Skew Heap е опростен вариант на Leftist Heap. * Идея: Не е нужно да пазим и поддържаме точната стойност на \(dist\). Вместо това, ние винаги разменяме лявото и дясното дете след сливане. * Това е саморегулираща се структура (подобно на Splay дърветата). * Няма гаранция за логаритмична височина в най-лошия случай (\(O(N)\)), но амортизираната сложност е \(O(\log N)\).

2.1. Имплементация

Кодът е изключително кратък и елегантен:

struct SkewNode {
    int val;
    SkewNode *left, *right;
    SkewNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

SkewNode* skew_merge(SkewNode* a, SkewNode* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->val > b->val) swap(a, b);

    // Сливаме дясното дърво с b
    a->right = skew_merge(a->right, b);

    // Винаги разменяме децата (това осигурява амортизирания баланс)
    swap(a->left, a->right);

    return a;
}
Това е препоръчителната структура за състезания, ако ви трябва обединяема пирамида, поради простотата си.

3. Binomial Heap (Биномиална пирамида)

Биномиалната пирамида е колекция от биномиални дървета. * Биномиално дърво от ред \(k\) (\(B_k\)) се дефинира рекурсивно: * \(B_0\) е един възел. * \(B_k\) се получава от две дървета \(B_{k-1}\), като коренът на едното става дете на корена на другото. * Има точно \(2^k\) възела. * Всеки хийп се представя като сбор от уникални биномиални дървета (подобно на двоичния запис на броя елементи).

Операцията merge наподобява двоично събиране. Ако и двете пирамиди имат дърво от ред \(k\), те се сливат в дърво от ред \(k+1\). Сложност: \(O(\log N)\). Биномиалните пирамиди са основата за по-сложните Fibonacci Heaps, които постигат \(O(1)\) за операция decrease_key.

4. Treap като пирамида

Тъй като Treap (Decartes Tree) поддържа операциите split и merge за \(O(\log N)\), той може лесно да се използва като приоритетна опашка. * Използваме стойностите като ключове за BST структурата. * Приоритетите (случайните числа) поддържат баланса. * merge на две дървета изисква всички ключове в едното да са по-малки от тези в другото (което не е винаги вярно за произволни хийпове), така че стандартният Treap не е директен заместител на Mergeable Heap за произволни данни, освен ако не се модифицира.

Въпреки това, Randomized Meldable Heap е вариация, където при сливане на два възела, решението кой да стане корен (ако стойностите са равни или близки) или в кое поддърво да се продължи, се взима на случаен принцип. Това работи много подобно на Skew Heap, но със случайност вместо безусловна размяна.

5. Сравнение и Приложение

Структура Insert Pop Min Merge Decrease Key Сложност на кода
Binary Heap \(O(\log N)\) \(O(\log N)\) \(O(N)\) \(O(\log N)\) Нисък (STL)
Leftist Heap \(O(\log N)\) \(O(\log N)\) \(O(\log N)\) \(O(\log N)\) Среден
Skew Heap \(O(\log N)^*\) \(O(\log N)^*\) \(O(\log N)^*\) \(O(\log N)^*\) Нисък
Fibonacci \(O(1)\) \(O(\log N)\) \(O(1)\) \(O(1)\) Много Висок

\(^*\) Амортизирана сложност.

Кога да използваме Mergeable Heap? 1. В задачи, изискващи обединяване на множества и търсене на минимум във всяко (напр. "Monkey King" в SPOJ). 2. При оптимизирани графиви алгоритми.

За състезателни цели: Skew Heap е най-добрият баланс между скорост на писане и производителност.

6. Fibonacci Heap (Фибоначиева пирамида)

Фибоначиевата пирамида е най-напредналата структура за приоритетна опашка, постигаща: * insert: \(O(1)\) амортизирана. * find_min: \(O(1)\). * decrease_key: \(O(1)\) амортизирана. * delete_min: \(O(\log N)\) амортизирана. * merge: \(O(1)\).

6.1. Защо е важна?

Използва се в: * Dijkstra алгоритъм: С Fibonacci Heap сложността става \(O(E + V \log V)\) вместо \(O((E + V) \log V)\). * Prim алгоритъм за MST: Същата оптимизация.

6.2. Проблем с практическото приложение

Въпреки теоретичната елегантност, имплементацията е много сложна и има голям константен фактор. В практиката обикновената Binary Heap или Pairing Heap са по-бързи за реални данни.

Извод: За състезания, Fibonacci Heap не си заслужава времето за имплементация.

7. Pairing Heap (Сдвоена пирамида)

Pairing Heap е по-проста алтернатива на Fibonacci Heap: * Почти същата амортизирана сложност. * Много по-лесна за имплементация. * В практиката често е по-бърза от Fibonacci Heap.

Основна идея

  • Всеки възел може да има произволен брой деца (не само 2).
  • Операцията merge е много проста: Свържете корена с по-малка стойност към другия.
  • При delete_min, всички деца се обединяват наново (two-pass pairing).
struct PairingNode {
    int val;
    PairingNode* child;
    PairingNode* sibling;

    PairingNode(int v) : val(v), child(nullptr), sibling(nullptr) {}
};

PairingNode* merge(PairingNode* a, PairingNode* b) {
    if (!a) return b;
    if (!b) return a;

    if (a->val > b->val) swap(a, b);

    b->sibling = a->child;
    a->child = b;
    return a;
}

8. Практически съвети

8.1. Кога да използваме обикновен Binary Heap?

  • За 95% от задачите - използвайте std::priority_queue.
  • Лесна имплементация, бърза в практиката, STL оптимизиран.

8.2. Кога да използваме Skew/Leftist Heap?

  • Когато merge е критична операция.
  • Примери: Union-Find с приоритети, алгоритми върху дървета.

8.3. Кога да използваме Fibonacci/Pairing Heap?

  • Ако имплементирате Dijkstra/Prim и ребрата са много повече от върховете (\(E >> V \log V\)).
  • Ако имате готова библиотека (boost::heap в C++).

9. Задачи за упражнение

  1. SPOJ RMQSQ: Range Minimum Query (може с Segment Tree, но и с Heap като алтернатива).
  2. Codeforces 643D: Проблем с merge на множества.
  3. POJ 3784: Running Median (два хийпа - max и min).
  4. SPOJ KQUERY: K-th element queries.

🏁 Заключение

Разбирането на различните типове пирамиди ви дава гъвкавост при решаване на сложни задачи. Ключовите точки:

  • Binary Heap: Вашият основен инструмент (чрез priority_queue).
  • Skew Heap: Най-простата обединяема пирамида - запомнете кода!
  • Leftist Heap: Леко по-сложна, но с гарантирана логаритмична сложност.
  • Fibonacci Heap: Теоретично перфектна, практически рядко използвана.

Препоръка: Подгответе си шаблон за Skew Heap и го тествайте предварително. В състезание просто го копирайте при нужда.

Владеенето на приоритетните опашки е критично за алгоритми като Dijkstra, Prim, Huffman кодиране и много задачи с динамично програмиране!