હીપ સોર્ટ કેવી રીતે કાર્ય કરે છે?

Question

Accepted Answer

**હીપ સોર્ટ** એરે માંથી **બાઈનરી હીપ** બનાવે છે, પછી સૌથી મોટા ઘટકને વારંવાર કાઢીને સમર્થિત ક્રમ મેળવે છે. તે **O(n log n)** માં ચાલે છે અને **in-place** છે.

## વિચાર

મેક્સ-હીપ રૂટ પર સૌથી મોટું ઘટક રાખે છે. હીપ બનાવો (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 કરતાં ધીમું હોય છે. એક જ હીપ રચના **priority queues** અને top-k ઘટકો શોધવા માટે શક્તિ આપે છે.

## શા માટે તે મહત્વપૂર્ણ છે

હીપ સોર્ટ એકમાત્ર સામાન્ય સોર્ટ છે જે worst-case O(n log n) અને in-place બંને છે, જે તેને મેમરી-પ્રતિબંધિત અથવા ગ્યારંટીવાળા-બાઉન્ડ સેટિંગમાં મૂલ્યવાન બનાવે છે.

હીપ રચના અંતર્ગત વ્યાપક રીતે ઉપયોગી છે — priority queues, Dijkstra ના અલ્ગોરિધમ અને streaming top-k.

તે વિચારને સમોવે છે કે યોગ્ય ડેટા સ્ટ્રક્ચર અલ્ગોરિધમને કાર્યક્ષમ બનાવે છે.