În acest articol vom prezenta structura de date numită heap, la fel și implementarea acesteia. La finalul articolului voi lăsa și o variantă STL a acestei structuri,dar e de preferat sa fie folosită abia după ce ați înțeles cum funcționează heap-urile.

Ce este un Heap?

Heapurile vin in doua forme: min-heap si max-heap. Astazi o sa ne focusam asupra primului, deoarece max-heapul este acelasi lucru, dar inversand operatia de comparare.

Intr-un min-heap, elementele sunt mai mici decat copii acestora, deci radacina heap-ului va fi intotdeauna elementul cel mai mic, privind heap-ul, de sus in jos putem observa cum elementele devin din ce in ce mai mari.

Un heap este de fapt un arbore binar, care are niște proprietăți specifice. Mai jos aveți o structură de heap:

Imaginea de mai sus este reprezentarea unui heap. Proprietățile sale specifice sunt următoarele:

• Toate nivelurile sunt complete, cu excepția ultimului nivel, care se completează începând de la stânga la dreapta, iar completarea se oprește la un anumit punct.
• Tatăl unui nod i > 1 este nodul [i/2], unde [] reprezintă partea întreagă a lui i/2. Fiii nodului i sunt 2*i respectiv 2*i+1. În cazul în care 2*i=numărul total de noduri, atunci nodul i are doar un singur fiu. În cazul în care 2*i > N, nodul i este frunză.
• Și nu în ultimul rând,  valoarea oricărui nod este mai mare sau egală cu valoarea oricărui fiu al său.

Ultima proprietate este cea mai importantă deoarece din ea rezultă faptul că rădăcina are cea mai mare valoare din tot heap-ul. Știind asta, putem să calculăm maximul dintr-un heap în O(1).

Operațiile despre care vom vorbii sunt:

• Crearea unei structuri de heap dintr-un vector oarecare in O(N)
• Eliminarea unui element in O(log N)
• Inserarea unui element in O(log N)

Dar înainte de asta trebuie să lămurim două proceduri care ne ajută în folosirea acestor operații.

Sift și percolate

Sift (sau UpHeap)

Există două proceduri care sunt specifice heap-urilor: funcția sift (a cerne) și funcția percolate (a se infiltra). Să presupunem că un vector are o structură de heap, cu excepția unui nod K care este mai mic decât unul din fiii sai. Vom folosi funcția  UpHeap pentru a așeza nodul K la locul potrivit.

Functia UpHeap primeste primește ca parametrii un heap H cu N noduri și nodul K și presupune ca ambii subarbori ai nodului K să aibă structura de heap corectă.

Rolul ei este să “cearnă” nodul K până la locul potrivit, interschimbând mereu nodul cu cel mai mare fiu al său până când nodul nu mai are fii (ajunge pe ultimul nivel in arbore) sau până când fiii săi au valori mai mici decât el. Mai jos aveți funcția de UpHeap (sau sift):

void UpHeap(int K)
{
    int Father = K / 2;
    if(Father && cmp(Val[Heap[K]],Val[Heap[Father]]))
    {
        Swap(K, Father);
        UpHeap(Father);
    }
}

Percolate (sau DownHeap)

Funcția DownHeap(percolate) se ocupă tocmai de fenomenul invers. Să presupunem că un heap are o “defecțiune” în sensul că observăm un nod care are o valoare mai mare decât tatăl său. Atunci, va trebui să interschimbăm cele două noduri folosind funcția  DownHeap. Mai jos aveți funcția de Downheap:

void DownHeap(int x)
{
    int Son = x * 2;
    if(Son + 1 <= N && cmp(Val[Heap[Son + 1]], Val[Heap[Son]]))
        Son += 1;
    if(Son <= N && cmp(Val[Heap[Son]], Val[Heap[x]]))
    {
        Swap(Son, x);
        DownHeap(Son);
    }
}

Acum putem vorbi despre fiecare operație în parte.

Crearea unei structuri de heap

Am spus că funcția  UpHeap presupune ca cei doi fii ai nodului pentru care este ea apelată să aibă structură de heap. Asta înseamnă că putem apela funcția  UpHeap pentru orice nod imediat superior nivelului frunzelor,  deoarece ele au structură de heap corectă. Apelând funcția  UpHeap pentru toate nodurile de deasupra frunzelor, vom obține deja o structură mai aranjată, asigurându-ne că pe ultimele două niveluri avem de-a face numai cu heap-uri. Apoi apelăm aceeași funcția pentru nodurile de pe al treilea nivel incepând de la frunze, apoi pentru cele de deasupra lor și așa mai departe până ajungem la radacină. Vom apela UpHeap începând de la nodul N/2 deoarece este ultimul nod care mai are fii. Restul nodurilor cu indici mai mari sunt frunze.

void BuildHeap(int M)
{
    for(int i = 1; i <= M; i++)
    {
        int v;
        cin >> v;
        Insert(v);
    }
}

Eliminarea unui nod din heap când știm poziția acestuia

Dacă vrem să eliminăm un element din heap, trebuie doar să refacem structura de heap. În locul nodului eliminat se va crea un gol, pe care trebuie să îl umplem cu un alt nod. Știind că toate nivelurile trebuie să fie complet ocupate, cu excepția ultimului, care poate fi gol doar în partea sa dreaptă, rezultă că singurul nod pe care îl putem pune în locul celui eliminat este ultimul din heap. Odată ce l-am pus in gaura facută, trebuie să ne asigurăm că acest nod “de umplutură” nu strică proprietatea de heap. Deci vom verifica: dacă nodul pus în loc este mai mare decât tatăl său, vom apela funcția  DownHeap. Altfel vom apela funcția UpHeap, în cazul în care nodul este mai mic decât unul din fiii sai.

void Erase(int x)
{
    Swap(x,N);
    N -= 1;
    DownHeap(x);
}

Inserarea unui element în heap

Această operație este mai simplă decât pare. Nu avem decât să-l așezăm pe poziția N+1 în vector și apoi să-l “promovăm” până la locul potrivit.

void Insert(int x)
{
    i += 1;
    Val[i] = x;

    N += 1;
    Heap[N] = i;
    Poz[i] = N;

    UpHeap(N);
}

De asemenea putem folosi și o alternativă STL. Una potrivită ar fi set-urile. Acestea sunt de fapt mulțimi menținute ca arbori binari echilibrați. Singurele dezavantaje ar fi că folosesc multă memorie și funcționează destul de încet. Mai jos aveți codul care este o soluție pentru problema Heapuri de pe Arhiva Educațională a site-ului infoarena.ro .

#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

const int NMax = 100005;
int N, Heap[NMax], Val[NMax], Poz[NMax], i;

inline void Swap(int x, int y)
{
    swap(Heap[x], Heap[y]);
    swap(Poz[Heap[x]], Poz[Heap[y]]);
}

bool cmp(int x,int y)
{
    return x < y;
}

void UpHeap(int x)
{
    int Father = x / 2;
    if(Father && cmp(Val[Heap[x]],Val[Heap[Father]]))
    {
        Swap(x, Father);
        UpHeap(Father);
    }
}

void DownHeap(int x)
{
    int Son = x * 2;
    if(Son + 1 <= N && cmp(Val[Heap[Son + 1]], Val[Heap[Son]]))
        Son += 1;
    if(Son <= N && cmp(Val[Heap[Son]], Val[Heap[x]]))
    {
        Swap(Son, x);
        DownHeap(Son);
    }
}

void Insert(int x)
{
    i += 1;
    Val[i] = x;

    N += 1;
    Heap[N] = i;
    Poz[i] = N;

    UpHeap(N);
}

void Erase(int x)
{
    Swap(x,N);
    N -= 1;
    DownHeap(x);
}

void Read()
{
    int Q, Case;
    fin >> Q;
    for(int i = 1; i <= Q; i++)
    {
        fin >> Case;
        if(Case == 1)
        {
            int x;
            fin >> x;
            Insert(x);
        }
        if(Case == 2)
        {
            int x;
            fin >> x;
            Erase(Poz[x]);
        }
        if(Case == 3)
            fout << Val[Heap[1]] << "\n";
    }
}

int main()
{
    Read();
    return 0;
}

#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>

#define NMAX 200005

using namespace std;

set <int> heap;

int n, poz[NMAX], k, a, x;

ifstream in("heapuri.in");
ofstream out("heapuri.out");

int main()
{
    in>>n;
    for(int i = 1; i <= n; i++)
    {
        in >> x;
        if(x == 1)
        {
            in >> a;
            heap.insert(a);
            poz[++k] = a;
        }
        else if(x == 2)
        {
            in >> a;
            heap.erase(poz[a]);
        }
        else
            out << *heap.begin() << '\n';
    }
    return 0;
}