Heap nedir ve bu nasıl bir öncelik sırasını uygular?

Question

Accepted Answer

**binary heap**, bir dizide depolanan ve **heap özelliğini** koruyan tam bir ikili ağaçtır: bir **min-heap**'te, her ebeveyn ≤ çocuklarıdır, bu nedenle **minimum her zaman kökün başındadır**. Bu, onu bir **priority queue**'nun standart uygulaması haline getirir.

## Dizi düzeni

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

## İşlemler

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

## Zaman Karmaşıklığı

| İşlem | Zaman |
|---|---|
| peek min/max | O(1) |
| push (insert) | O(log n) |
| pop (extract) | O(log n) |
| n öğeden heap oluştur | O(n) |

## Ne zaman kullanılır

- **Öncelik** göre planlama (örn. OS görev zamanlayıcıları).
- **Dijkstra / Prim** en kısa yol ve MST algoritmaları.
- **Top-K** sorunları ve akış medyanları.
- **Heap sort** (yerinde O(n log n)).

## Neden önemli

Bir heap, her şeyi tamamen sıralamadan sonraki en önemli öğeyi anında verir; bu, yeniden sıralamaktan çok daha ucuzdur.

Priority tarafından yönlendirilen algoritmaların omurgasıdır ve "k en büyük/en küçük" sorularına sık kullanılan bir mülakat aracıdır.

İşlem	Zaman
peek min/max	O(1)
push (insert)	O(log n)
pop (extract)	O(log n)
n öğeden heap oluştur	O(n)