হিপ সর্ট কীভাবে কাজ করে?

Question

Accepted Answer

**হিপ সর্ট** অ্যারে থেকে একটি **বাইনারি হিপ** তৈরি করে, তারপর বারবার সর্বোচ্চ উপাদান বের করে সর্টেড ক্রম তৈরি করে। এটি **O(n log n)** এ চলে এবং **ইন-প্লেস**।

## ধারণা

একটি ম্যাক্স-হিপ মূলে সবচেয়ে বড় উপাদান রাখে। হিপ তৈরি করুন (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 দ্বারা এটি ইন-প্লেসে করে।

## জটিলতা

- **সময়:** সকল ক্ষেত্রে O(n log n)। **স্পেস:** ইন-প্লেসে O(1)।

## ব্যবহার করার সময় / সমস্যা

ব্যবহার করুন যখন আপনার **গ্যারান্টিড O(n log n)** *এবং* **O(1) অতিরিক্ত স্মৃতি** প্রয়োজন (merge sort O(n) প্রয়োজন; quicksort O(n²) ঝুঁকি রাখে)। এটি **অস্থিতিশীল** এবং খারাপ ক্যাশ স্থানীয়তা রয়েছে, তাই এটি ব্যবহারিকভাবে quicksort এর চেয়ে প্রায়ই ধীর। একই হিপ **অগ্রাধিকার সারি** এবং শীর্ষ-k উপাদান খুঁজে পেতে শক্তি দেয়।

## কেন এটি গুরুত্বপূর্ণ

হিপ সর্ট একমাত্র সাধারণ সর্ট যা worst-case O(n log n) এবং ইন-প্লেস উভয়ই, এটি মেমরি-সীমাবদ্ধ বা গ্যারান্টিযুক্ত-সীমা সেটিংসে মূল্যবান করে তোলে।

নিম্নস্থ হিপ কাঠামো ব্যাপকভাবে উপযোগী — অগ্রাধিকার সারি, Dijkstra এর অ্যালগরিদম, এবং স্ট্রিমিং শীর্ষ-k।

এটি এই ধারণাকে দৃঢ় করে যে সঠিক ডেটা কাঠামো একটি অ্যালগরিদম দক্ষ করে তোলে।