Programare Competitivă

Heap (coadă de priorități)

Un heap este o structură de date care permite extragerea rapidă a elementului minim (min-heap) sau maxim (max-heap) dintr-o colecție dinamică.

Se mai numește și coadă de priorități - elementele au priorități, iar cel cu prioritatea cea mai mare (sau mică) este servit primul.

Aceasta este o lecție pur teoretică. Personal, nu mi-am implementat niciodată propriul min-heap - am folosit mereu priority_queue din STL, pe care îl veți învăța mai târziu.

De ce avem nevoie de heap?

Dacă vrem mereu minimul/maximul:

Operație Vector nesortat Vector sortat Heap
Insert O(1) O(n) O(log n)
Extract min/max O(n) O(1) O(log n)
Peek min/max O(n) O(1) O(1)

Heap-ul oferă echilibrul între inserare și extragere.

Structura unui heap

Un heap este un arbore binar complet stocat într-un vector, cu proprietatea:

Min-heap: fiecare nod este mai mic sau egal cu copiii săi.

Vector: [_, 1, 3, 2, 7, 6, 5, 4]  (indexat de la 1)

Arborele:
           1
         /   \
        3     2
       / \   / \
      7   6 5   4

Rădăcina (poziția 1) conține minimul.

Relații de indici

Pentru nodul de pe poziția i:

  • Părinte: i / 2
  • Copil stâng: 2 * i
  • Copil drept: 2 * i + 1
i=1: copii = 2, 3
i=2: copii = 4, 5    părinte = 1
i=3: copii = 6, 7    părinte = 1
i=4:                  părinte = 2

De ce vector? Un arbore binar complet se stochează perfect în vector: poziția i are copiii pe 2*i și 2*i+1. Nu avem nevoie de pointeri.

Operații pe min-heap

Insert (adăugare)

  1. Punem elementul la final (pe poziția n + 1).
  2. Urcăm (sift up): cât timp e mai mic decât părintele, le interschimbăm.
Insert 0 în heap [1, 3, 2, 7, 6, 5, 4]:

Pasul 1: punem la final
[1, 3, 2, 7, 6, 5, 4, 0]
                       ↑
Pasul 2: 0 < 7 (părinte) → swap
[1, 3, 2, 0, 6, 5, 4, 7]
            ↑
Pasul 3: 0 < 3 (părinte) → swap
[1, 0, 2, 3, 6, 5, 4, 7]
   ↑
Pasul 4: 0 < 1 (părinte) → swap
[0, 1, 2, 3, 6, 5, 4, 7]
 ↑ rădăcina - stop

Extract min (extragere minim)

  1. Minimul e pe poziția 1 (rădăcina). Îl salvăm.
  2. Punem ultimul element pe poziția 1.
  3. Coborâm (sift down): cât timp e mai mare decât un copil, interschimbăm cu copilul mai mic.
Extract min din [0, 1, 2, 3, 6, 5, 4, 7]:

Pasul 1: salvăm 0, punem ultimul pe rădăcină
[7, 1, 2, 3, 6, 5, 4]
 ↑
Pasul 2: 7 > min(1, 2) = 1 → swap cu 1
[1, 7, 2, 3, 6, 5, 4]
    ↑
Pasul 3: 7 > min(3, 6) = 3 → swap cu 3
[1, 3, 2, 7, 6, 5, 4]
         ↑ frunză - stop

Implementare completă

int heap[100001];
int dim = 0;

void siftUp(int poz) {
    while (poz > 1 && heap[poz] < heap[poz / 2]) {
        int aux = heap[poz];
        heap[poz] = heap[poz / 2];
        heap[poz / 2] = aux;
        poz = poz / 2;
    }
}

void siftDown(int poz) {
    while (2 * poz <= dim) {
        int copil = 2 * poz;
        // Alegem copilul mai mic
        if (copil + 1 <= dim && heap[copil + 1] < heap[copil])
            copil++;
        // Dacă părintele e mai mare, swap
        if (heap[poz] > heap[copil]) {
            int aux = heap[poz];
            heap[poz] = heap[copil];
            heap[copil] = aux;
            poz = copil;
        } else {
            break;
        }
    }
}

void insert(int x) {
    dim++;
    heap[dim] = x;
    siftUp(dim);
}

int getMin() {
    return heap[1];
}

void extractMin() {
    heap[1] = heap[dim];
    dim--;
    siftDown(1);
}

Exemplu complet: cele mai mici K elemente

Citim n numere și afișăm cele mai mici K dintre ele.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int heap[100001];
int dim;

void siftUp(int poz) {
    while (poz > 1 && heap[poz] < heap[poz / 2]) {
        int aux = heap[poz];
        heap[poz] = heap[poz / 2];
        heap[poz / 2] = aux;
        poz = poz / 2;
    }
}

void siftDown(int poz) {
    while (2 * poz <= dim) {
        int copil = 2 * poz;
        if (copil + 1 <= dim && heap[copil + 1] < heap[copil])
            copil++;
        if (heap[poz] > heap[copil]) {
            int aux = heap[poz];
            heap[poz] = heap[copil];
            heap[copil] = aux;
            poz = copil;
        } else break;
    }
}

void insert(int x) {
    dim++;
    heap[dim] = x;
    siftUp(dim);
}

int getMin() {
    return heap[1];
}

void extractMin() {
    heap[1] = heap[dim];
    dim--;
    siftDown(1);
}

int main()
{
    int n, k;
    fin >> n >> k;

    dim = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        insert(x);
    }

    for (int i = 1; i <= k; i++) {
        fout << getMin() << " ";
        extractMin();
    }

    return 0;
}

date.in:

8 3
5 3 8 1 9 2 7 4

date.out:

1 2 3

Max-heap

Pentru max-heap, inversăm comparațiile:

void siftUp(int poz) {
    while (poz > 1 && heap[poz] > heap[poz / 2]) { // > în loc de <
        // swap ...
        poz = poz / 2;
    }
}

void siftDown(int poz) {
    while (2 * poz <= dim) {
        int copil = 2 * poz;
        if (copil + 1 <= dim && heap[copil + 1] > heap[copil]) // > în loc de <
            copil++;
        if (heap[poz] < heap[copil]) { // < în loc de >
            // swap ...
            poz = copil;
        } else break;
    }
}

Heap Sort

Sortăm un vector folosind un heap:

  1. Inserăm toate elementele în heap - O(n log n)
  2. Extragem minimul de n ori - O(n log n)
// Inserăm tot
for (int i = 1; i <= n; i++)
    insert(v[i]);

// Extragem sortat
for (int i = 1; i <= n; i++) {
    v[i] = getMin();
    extractMin();
}

Complexitate: O(n log n) - la fel ca Merge Sort și Quick Sort.

Build heap în O(n)

În loc să inserăm elementele unul câte unul (O(n log n)), putem construi heap-ul direct din vector în O(n) folosind sift down de la jumătate spre 1:

// Copiem vectorul în heap
for (int i = 1; i <= n; i++)
heap[i] = v[i];
dim = n;

// Build heap
for (int i = n / 2; i >= 1; i--)
siftDown(i);

Aceasta e mai eficientă: O(n) în loc de O(n log n). Demonstrația matematică arată că suma operațiilor de sift down converge la O(n).

Mediana curentă

Problemă avansată: primim numere unul câte unul și după fiecare trebuie să afișăm mediana (elementul din mijloc dacă le-am sorta).

Ideea: folosim două heap-uri:

  • Un max-heap pentru jumătatea stângă (elementele mici)
  • Un min-heap pentru jumătatea dreaptă (elementele mari)

Mediana e mereu în vârful unuia dintre ele.

Greșeli frecvente

1. Indexarea de la 0

Formulele 2*i, 2*i+1, i/2 funcționează corect doar cu indexare de la 1. Dacă indexezi de la 0, formulele sunt 2*i+1, 2*i+2, (i-1)/2.

2. Sift down - uitarea comparării ambilor copii

// GREȘIT - alegem mereu copilul stâng
int copil = 2 * poz;

// CORECT - alegem copilul mai mic/mare
int copil = 2 * poz;
if (copil + 1 <= dim && heap[copil + 1] < heap[copil])
    copil++;

3. Extract fără sift down

heap[1] = heap[dim]; dim--;
// LIPSEȘTE: siftDown(1);

Fără sift down, structura de heap se distruge.

4. Confuzia min-heap / max-heap

Min-heap: rădăcina = minimul (fiecare nod e mai mic decât copiii). Max-heap: rădăcina = maximul (fiecare nod e mai mare decât copiii).

Comparațiile din sift up/down sunt inversate între cele două.

Ce să reții

  • Heap = arbore binar complet stocat în vector cu proprietatea de heap.
  • Min-heap: rădăcina = minimul. Max-heap: rădăcina = maximul.
  • Insert: O(log n) - adaugă la final + sift up.
  • Extract: O(log n) - pune ultimul pe rădăcină + sift down.
  • Peek: O(1) - rădăcina.
  • Relații de indici: părinte = i/2, copii = 2*i și 2*i+1.
  • Heap Sort: O(n log n).
  • Build heap: O(n) cu sift down de la jumătate.

Probleme

pbinfoTaxe2→

pbinfoLee2→

pbinfoTaxa→

Cuprins Inapoi Inainte