Çfarë është një heap dhe si implementon atë një red me prioritet?

Question

IT Interview Practice · Accepted Answer

Një **binary heap** është një pemë binare e plotë e ruajtur në një grup që mban **heap property**: në një **min-heap**, çdo prind është ≤ fëmijëve të tij, kështu **minimumi është gjithmonë në rrënjën**. Kjo e bën atë implementimin standard të një **red me prioritet**.

## Paraqitja në grup

```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
```

## Operacionet

```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
```

## Kompleksiteti kohor

| Operacioni | Koha |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| ndërtimi i heap nga n elementë | O(n) |

## Kur ta përdorni

- **Planifikimi** sipas prioritetit (p.sh. OS task schedulers).
- **Dijkstra / Prim** algoritmet për rrugën më të shkurtër dhe MST.
- Probleme **Top-K** dhe mediana e rrjedhës.
- **Heap sort** (në vend O(n log n)).

## Pse është i rëndësishëm

Heap ju jep elementin më të rëndësishëm tjetër menjëherë pa ruajtur gjithçka plotësisht të renditur, e cila është shumë më lirë se ripërendosja.

Ai është themeli i algoritmeve të drejtuar nga prioriteti dhe një mjet i shpeshte në intervista për pyetjet "k më të mëdha/më të vogla".

Operacioni	Koha
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
ndërtimi i heap nga n elementë	O(n)

Paraqitja në grup

Operacionet

Kompleksiteti kohor

Kur ta përdorni

Pse është i rëndësishëm

Pyetje të ngjashme