ਹੀਪ ਸੌਰਟ ਕਿਵੇਂ ਕੰਮ ਕਰਦਾ ਹੈ?

Question

Accepted Answer

**Heap sort** array ਤੋਂ ਇੱਕ **binary heap** ਬਣਾਉਂਦਾ ਹੈ, ਫਿਰ ਬਾਰ ਬਾਰ ਅਧਿਕਤਮ ਕੱਢਦਾ ਹੈ ਤਾਂ ਜੋ ਸਾਜ਼ਿਸ਼ੀ ਕ੍ਰਮ ਪੈਦਾ ਹੋਵੇ। ਇਹ **O(n log n)** ਵਿੱਚ ਚਲਦਾ ਹੈ ਅਤੇ **in-place** ਹੈ।

## ਵਿਚਾਰ

ਇੱਕ max-heap ਸਭ ਤੋਂ ਵੱਡਾ ਤੱਤ ਮੂਲ ਵਿਖੇ ਰੱਖਦਾ ਹੈ। Heap ਬਣਾਓ (O(n)), ਫਿਰ ਮੂਲ ਨੂੰ ਅੰਤ ਵਿੱਚ ਬਦਲੋ, heap ਨੂੰ ਸੁੰਗੜੋ, ਅਤੇ re-heapify (sift down) ਕਰੋ — n ਵਾਰ।

## ਉਦਾਹਰਣ

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

ਇੱਕ ਕਲਾਸਿਕ ਲਾਗੂਕਰਨ ਇਸ ਨੂੰ array ਦੇ ਅੰਦਰ sift down ਕਰਕੇ ਜਗ੍ਹਾ ਤੇ ਕਰਦਾ ਹੈ।

## ਗੁੰਝਲਦਾਰੀ

- **ਸਮਾਂ:** ਸਾਰੀ ਸਥਿਤੀ ਵਿੱਚ O(n log n)। **ਸਪੇਸ:** O(1) in-place।

## ਕਦੋਂ ਵਰਤੋ / ਰੁਕਾਵਟਾਂ

ਜਦੋਂ ਤੁਹਾਨੂੰ **guaranteed O(n log n)** *ਅਤੇ* **O(1) ਵਾਧੂ ਮੈਮੋਰੀ** ਦੀ ਲੋੜ ਹੋ ਤਾਂ ਵਰਤੋ (merge sort ਨੂੰ O(n) ਚਾਹੀਦਾ ਹੈ; quicksort O(n²) ਦਾ ਜੋਖਮ ਲੈਂਦਾ ਹੈ)। ਇਹ **not stable** ਹੈ ਅਤੇ ਬਹੁਤ ਮਾੜੀ cache locality ਹੈ, ਇਸ ਲਈ ਇਹ ਅਭਿਆਸ ਵਿੱਚ quicksort ਨਾਲੋਂ ਅਕਸਰ ਹੌਲਾ ਹੈ। ਉਸੇ heap ਨੂੰ **priority queues** ਅਤੇ top-k ਤੱਤ ਲੱਭਣ ਦਾ ਸ਼ਕਤੀ ਦਿੰਦਾ ਹੈ।

## ਕਿਉਂ ਇਹ ਮਹੱਤਵਪੂਰਨ ਹੈ

Heap sort ਸਿਰਫ ਆਮ ਸਾਜ਼ਿਸ਼ ਹੈ ਜੋ worst-case O(n log n) ਅਤੇ in-place ਦੋਵੇ ਹੈ, ਜੋ ਇਸ ਨੂੰ ਮੈਮੋਰੀ-ਸੀਮਿਤ ਜਾਂ ਗ੍ਰੰਟੀਡ-ਬਾਊਂਡ ਸੈਟਿੰਗਜ ਵਿੱਚ ਮੁੱਲਵਾਨ ਬਣਾਉਂਦਾ ਹੈ।

Heap ਬਣਤਰ ਹੇਠਾਂ ਵਿਆਪਕ ਤੌਰ ਤੇ ਲਾਭਦਾਇਕ ਹੈ — priority queues, Dijkstra ਦਾ ਅਲਗੋਰਿਦਮ, ਅਤੇ streaming top-k।

ਇਹ ਵਿਚਾਰ ਨੂੰ ਪੱਕਾ ਕਰਦਾ ਹੈ ਕਿ ਸਹੀ ਡੇਟਾ ਸਟ੍ਰਕਚਰ ਇੱਕ ਅਲਗੋਰਿਦਮ ਨੂੰ ਕੁਸ਼ਲ ਬਣਾਉਂਦਾ ਹੈ।