Heap sort کیسے کام کرتا ہے؟

Question

Accepted Answer

**Heap sort** array سے ایک **binary heap** بناتا ہے، پھر بار بار maximum نکال کر sorted ترتیب بناتا ہے۔ یہ **O(n log n)** میں چلتا ہے اور **in-place** ہے۔

## خیال

ایک max-heap سب سے بڑے عنصر کو root میں رکھتا ہے۔ Heap بنائیں (O(n))، پھر root کو آخر میں swap کریں، 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]
```

ایک classic implementation اسے array کے اندر sift down کر کے in place کرتا ہے۔

## Complexity

- **Time:** تمام صورتوں میں O(n log n)۔ **Space:** in-place میں O(1)۔

## کب استعمال کریں / نقائص

استعمال کریں جب آپ کو **guaranteed O(n log n)** *اور* **O(1) extra memory** کی ضرورت ہو (merge sort کو O(n) چاہیے؛ quicksort کو O(n²) کا خطرہ)۔ یہ **stable نہیں** ہے اور cache locality خراب ہے، تو عملی طور پر اکثر quicksort سے سست ہے۔ یہی heap **priority queues** اور top-k عناصر تلاش کرنے میں بھی کام آتا ہے۔

## یہ کیوں اہم ہے

Heap sort واحد عام sort ہے جو worst-case O(n log n) اور in-place دونوں ہے، یہ memory-constrained یا guaranteed-bound حالات میں قیمتی ہے۔

اس کے نیچے heap ساخت وسیع طور پر مفید ہے — priority queues، Dijkstra's algorithm، اور streaming top-k۔

یہ اس خیال کو مضبوط کرتا ہے کہ صحیح data structure ایک algorithm کو موثر بناتا ہے۔