हीप सॉर्ट कैसे काम करता है?

Question

Accepted Answer

**हीप सॉर्ट** सरणी से एक **बाइनरी हीप** बनाता है, फिर क्रमबद्ध क्रम प्राप्त करने के लिए अधिकतम को बार-बार निकालता है। यह **O(n log n)** में चलता है और **in-place** है।

## विचार

एक max-heap मूल पर सबसे बड़े तत्व को रखता है। हीप बनाएं (O(n)), फिर मूल को अंत में स्वैप करें, हीप को सिकोड़ें, और पुनः-हीपिफाई (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]
```

एक शास्त्रीय कार्यान्वयन सरणी के भीतर sift down करके इसे in-place करता है।

## जटिलता

- **समय:** O(n log n) सभी मामलों में। **स्पेस:** O(1) in-place।

## कब उपयोग करें / खतरे

जब आपको **गारंटीयुक्त O(n log n)** *और* **O(1) अतिरिक्त मेमोरी** की आवश्यकता हो (merge sort को O(n) चाहिए; quicksort को O(n²) का खतरा है)। यह **स्थिर नहीं** है और कमजोर cache locality है, इसलिए व्यावहारिक रूप से यह अक्सर quicksort से धीमा है। समान हीप संरचना **प्राथमिकता कतारें** और शीर्ष-k तत्वों की खोज को शक्ति देती है।

## यह क्यों महत्वपूर्ण है

हीप सॉर्ट एकमात्र सामान्य सॉर्ट है जो worst-case O(n log n) और in-place दोनों है, जो इसे मेमोरी-सीमित या गारंटीयुक्त-बाउंड सेटिंग में मूल्यवान बनाता है।

अंतर्निहित हीप संरचना व्यापक रूप से उपयोगी है — प्राथमिकता कतारें, Dijkstra का एल्गोरिदम और स्ट्रीमिंग top-k।

यह विचार को सीमेंट करता है कि सही डेटा संरचना एक एल्गोरिदम को कुशल बनाती है।