Ce este un heap și cum implementează o coadă de prioritate?

Question

Accepted Answer

Un **binary heap** este un arbore binar complet stocat într-un array care menține **proprietatea heap**: într-un **min-heap**, fiecare părinte este ≤ copiilor săi, deci **minimul se află întotdeauna la rădăcină**. Aceasta îl face implementarea standard a unei **cozi de prioritate**.

## Dispunerea în array

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## Operații

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## Complexitate

| Operație | Timp |
|---|---|
| peek min/max | O(1) |
| push (inserare) | O(log n) |
| pop (extragere) | O(log n) |
| construire heap din n elemente | O(n) |

## Când se folosește

- **Planificarea** după prioritate (de ex. planificatoarele de task-uri ale SO).
- Algoritmi **Dijkstra / Prim** pentru cele mai scurte drumuri și ARCm.
- Probleme **Top-K** și mediane în streaming.
- **Heap sort** (in-place O(n log n)).

## De ce contează

Un heap îți oferă următorul element cel mai important instantaneu, fără a menține totul complet sortat, ceea ce este mult mai ieftin decât re-sortarea.

Este coloana vertebrală a algoritmilor condui de prioritate și un instrument frecvent în interviuri pentru întrebări de tip "k cel mai mare/mic".

Operație	Timp
peek min/max	O(1)
push (inserare)	O(log n)
pop (extragere)	O(log n)
construire heap din n elemente	O(n)