हीप सॉर्ट कसरी काम गर्छ?

Question

Accepted Answer

**Heap sort** ले array बाट **binary heap** बनाउँछ, त्यसपछि बारम्बार अधिकतम निकाल्छ र क्रमबद्ध क्रम उत्पादन गर्छ। यो **O(n log n)** मा चल्छ र **in-place** हो।

## विचार

Max-heap ले सबैभन्दा ठूलो तत्व root मा राख्छ। Heap बनाउनुहोस् (O(n)), त्यसपछि root लाई अन्तमा स्वैप गर्नुहोस्, 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 दुवै हो, जसले यसलाई मेमोरी-सीमित वा guaranteed-bound सेटिङहरूमा मूल्यवान बनाउँछ।

Heap संरचना तल व्यापक रूपमा उपयोगी छ — priority queues, Dijkstra को एल्गोरिदम, र streaming top-k।

यो विचार सिमेन्ट गर्छ कि सही डेटा संरचना एल्गोरिदम प्रभावी बनाउँछ।