Heap sort ina fanya kazi vipi?

Question

Accepted Answer

**Heap sort** inajengana **binary heap** kutoka kwa safu, kisha mara kwa mara inatoa maximum ili kuzalisha mpangilio uliofungwa. Inakimbia katika **O(n log n)** na ni **mahali mahali**.

## Wazo

Max-heap inahifadhi kipengele kikubwa zaidi katika mzizi. Jeneza heap (O(n)), kisha badilisha mzizi hadi ncha, kupunguza heap, na kuweka upya (sift down) — n mara.

## Mfano

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

Utekelezaji wa kawaida unafanya hivyo mahali kwa kuhamisha chini ndani ya safu.

## Ugumu

- **Muda:** O(n log n) katika visa vyote. **Nafasi:** O(1) mahala mahala.

## Wakati wa kutumia / mitego

Tumia wakati unahitaji **O(n log n) iliyohakikishwa** *na* **O(1) kumbukumbu ya ziada** (merge sort inahitaji O(n); quicksort ina hatari ya O(n²)). Sio **imara** na ina uzuri wa cache mbaya, kwa hivyo ni mara nyingi polepole katika mazoezi kuliko quicksort. Heap sawa inaendesha **prioritized queues** na kutafuta vipengele vya juu-k.

## Kwa nini kinakamatia

Heap sort ndiyo upangaji wa kawaida pekee ambao ni kwa upande mmoja O(n log n) katika hali mbaya na mahala mahala, ikifanya iwe ya thamani katika mipango yenye kumbukumbu iliyozuiwa au iliyohakikishwa.

Mundo wa heap ni mahususi — prioritized queues, Dijkstra's algorithm, na streaming top-k.

Inakamatisha wazo kwamba struktura sahihi ya data hufanya algoriti kuwa mahususi.