Heap sort nasıl çalışır?

Question

Accepted Answer

**Heap sort**, diziden bir **binary heap** oluşturur, ardından sıralanmış sıra üretmek için en büyük öğeyi tekrar tekrar çıkarır. **O(n log n)** içinde çalışır ve **yerinde** dir.

## Fikir

Bir max-heap en büyük öğeyi kökte tutar. Heap oluşturun (O(n)), kökü sona değiştirin, heap i küçültün ve yeniden heapify edin (sift down) — n kez.

## Örnek

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap in O(n)
    return [heapq.heappop(arr)       # pop smallest n times
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

Klasik bir uygulama bunu dizi içinde sift down yaparak yerinde yapar.

## Karmaşıklık

- **Zaman:** Tüm durumlarda O(n log n). **Alan:** Yerinde O(1).

## Ne zaman kullanılır / Tuzaklar

**Garantili O(n log n)** *ve* **O(1) ekstra bellek** gerektiğinde kullanın (merge sort O(n) gerektirir; quicksort O(n²) riski taşır). **Stabil değildir** ve zayıf cache lokalitesine sahiptir, bu nedenle pratikte quicksort tan genellikle daha yavaştır. Aynı heap, **öncelik kuyrukları** ve top-k öğelerini bulma işlevini sağlar.

## Neden önemli

Heap sort, hem en kötü durumda O(n log n) hem de yerinde olan tek ortak sıralamadır; bu da bellek kısıtlı veya garantili sınır ayarlarında değerli hale getirir.

Heap yapısı yaygın şekilde faydalıdır — öncelik kuyrukları, Dijkstra algoritması ve streaming top-k.

Doğru veri yapısının bir algoritmayı verimli hale getirdiği fikrini pekiştirir.