Heap sort कसे कार्य करते?

Question

Accepted Answer

**Heap sort** अॅरे पासून **binary heap** तयार करते, नंतर क्रमवारीत क्रमाची निर्मिती करण्यासाठी जास्तीत जास्त वारंवार काढून घेते. हे **O(n log n)** मध्ये चालते आणि **in-place** आहे.

## कल्पना

Max-heap मूळ येथे सर्वात मोठा घटक ठेवते. Heap तयार करा (O(n)), नंतर मूळ शेवटी स्वॅप करा, heap संकुचित करा, आणि पुन्हा-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]
```

क्लासिक अंमलीकरण हे अॅरे मध्ये 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 पेक्षा अनेकदा धीमे आहे. तोच heap **priority queue** आणि top-k घटक शोधण्याचे शक्तिमान ठरते.

## हे महत्वाचे का आहे

Heap sort हा एकमात्र सामान्य सॉर्ट आहे जो worst-case O(n log n) आणि in-place दोन्ही आहे, ज्यामुळे हे मेमरी-अवरोधित किंवा गॅरेंटीड-बाउंड सेटिंगमध्ये मूल्यवान आहे.

खाली असलेली heap रचना व्यापकपणे उपयोगी आहे — priority queue, Dijkstra चा अल्गोरिदम, आणि streaming top-k.

हे कल्पना स्थापित करते की योग्य डेटा रचना अल्गोरिदम कार्यक्षम बनवते.