Kif taħdem heap sort?

Question

Accepted Answer

**Heap sort** tibni **binary heap** mill-array, imbagħad ripetutament testratt il-massimu biex tipproduċi ordni sortata. Taħdem f' **O(n log n)** u hija **in-place**.

## L-idea

Max-heap żamm l-element l-akbar fil-għerq. Ibni l-heap (O(n)), imbagħad isbadal ir-għerq sal-aħħar, iżvantaġġ il-heap, u erġa' heapify (sift down) — n darbiet.

## Eżempju

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

Implementazzjoni klassika tagħmilha in-place billi tagħmel sift down ġewwa l-array.

## Kumplessità

- **Ħin:** O(n log n) fil-każi kollha. **Spazju:** O(1) in-place.

## Meta tuża / xbieli

Uża meta għandek bżonn **O(n log n) garantit** *u* **O(1) memorja addizzjonali** (merge sort bżonnu O(n); quicksort jiriskja O(n²)). **Mhix stabbli** u għandha cache locality ħażin, allura ħafna drabi ikun ħa bil-mod fil-prattika minn quicksort. L-istess heap jipprovdi qawwa **priority queue** u sib tal-elementi top-k.

## Għaliex hija importanti

Heap sort huwa l-uniku sort komuni li huwa kemm worst-case O(n log n) kif ukoll in-place, li jagħmilha ta' valur f'settings memory-constrained jew guaranteed-bound.

L-istruttura heap taħt hija ta' utilità wiesgħa — priority queue, algoritmu ta' Dijkstra, u streaming top-k.

Hi tiċċimenta l-idea li l-istruttura tad-data t-tajba tagħmel algoritmu effitsyenti.