Heap sort ఎలా పనిచేస్తుంది?

Question

Accepted Answer

**Heap sort** శ్రేణి నుండి **binary heap** నిర్మిస్తుంది, ఆపై ఆర్డర్ చేయబడిన క్రమం ఉత్పత్తి చేయడానికి పదే పదే గరిష్ఠమాన్ని సంగ్రహిస్తుంది. ఇది **O(n log n)** లో నడుస్తుంది మరియు **ఇన్-ప్లేస్**.

## ఆలోచన

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 ద్వారా ఇన్-ప్లేస్ లో చేస్తుంది.

## సంక్లిష్టత

- **సమయం:** అన్ని సందర్భాలలో O(n log n). **స్థలం:** ఇన్-ప్లేస్ O(1).

## ఎప్పుడు ఉపయోగించాలి / విధులు

**ఖాతరు O(n log n)** *మరియు* **O(1) అదనపు మెమరీ** అవసరమైనప్పుడు ఉపయోగించండి (merge sort కు O(n) అవసరం; quicksort O(n²) ఝుమ్మివేస్తుంది). ఇది **స్థిరంగా లేనిది** మరియు చెత్త కాష్ లోకాలిటీని కలిగి ఉంది, కాబట్టి ఇది ఆచరణలో quicksort కంటే తరచుగా నెమ్మదిగా ఉంటుంది. అదే heap **priority queues** మరియు top-k మూలకాలను కనుగొనడానికి శక్తిని ఇస్తుంది.

## ఎందుకు ఇది ముఖ్యమైనది

Heap sort అనేది సాధారణ సార్ట్ లో ఏకైక ఒక, ఇది చెత్త కేసు O(n log n) మరియు ఇన్-ప్లేస్, ఇది మెమరీ-నిరోధకమైన లేదా ఖాతరు-బౌండ్ సెట్ టింగ్ లలో విలువైనది.

Heap నిర్మాణం విస్తృతంగా ఉపయోగకరమైనది — priority queues, Dijkstra ల అల్గోరిథ్‌మ మరియు స్ట్రీమింగ్ top-k.

ఇది సరైన డేటా నిర్మాణం అల్గోరిథ్‌మను సమర్థవంతం చేస్తుందనే ఆలోచనను నిర్ధారిస్తుంది.