হিপ সর্ট (Heap Sort) বাইনারি হিপ (Binary Heap) ডেটা স্ট্রাকচারের ওপর ভিত্তি করে তৈরি একটি সর্টিং অ্যালগরিদম। বাইনারি হিপে, ম্যাক্স হিপ (Max Heap)-এ পেরেন্ট নোডের চাইল্ড নোডগুলো পেরেন্ট থেকে ছোট বা সমান হয়; আবার মিন হিপ (Min Heap)-এ চাইল্ড নোডগুলো পেরেন্ট থেকে বড় বা সমান হয়।
উদাহরণ: ধাপে ধাপে হিপ সর্ট
সর্ট করার আগে ১০ উপাদানের মূল অ্যারে:
| 20 | 7 | 1 | 54 | 10 | 15 | 90 | 23 | 77 | 25 |
এই অ্যারেটি max-heapify ব্যবহার করে একটি বাইনারি ম্যাক্স হিপে রূপান্তর করা হয়। ম্যাক্স হিপ অ্যারে রিপ্রেজেন্টেশন:
| 90 | 77 | 20 | 54 | 25 | 15 | 1 | 23 | 7 | 10 |
ম্যাক্স হিপের রুট এলিমেন্ট (সর্বোচ্চ মান) বের করে অ্যারার শেষে রাখা হয়। তারপর বাকি এলিমেন্টগুলোর সাথে আবার max-heapify কল করা হয়। এই প্রক্রিয়া চলতে থাকে যতক্ষণ না পুরো অ্যারেটি সর্ট হয়ে যায়। সর্ট হওয়া অ্যারে:
| 1 | 7 | 10 | 15 | 20 | 23 | 25 | 54 | 77 | 90 |
উদাহরণ কোড
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int temp;
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
int temp;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements from heap one by one
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
int n = 10;
int i;
cout << "দেওয়া অ্যারে: " << endl;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
heapSort(arr, n);
cout << "\nসর্ট করা অ্যারে: \n";
for (i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}আউটপুট
দেওয়া অ্যারে: 20 7 1 54 10 15 90 23 77 25 সর্ট করা অ্যারে: 1 7 10 15 20 23 25 54 77 90
কোড ব্যাখ্যা
heapify() ফাংশন
এই ফাংশনটি একটি সাব-ট্রিকে ম্যাক্স হিপ প্রোপার্টি বজায় রাখে। এটি রিকার্সিভ। পেরামিটার i হলো রুট নোডের ইনডেক্স। বাম চাইল্ড = 2*i+1, ডান চাইল্ড = 2*i+2। যদি কোনো চাইল্ড পেরেন্ট থেকে বড় হয়, তবে স()(অداور করে আবার সাব-ট্রিকে heapify কল করা হয়।
heapSort() ফাংশন
প্রথমে নন-লিফ নোডগুলো থেকে (i = n/2 - 1) শুরু করে রুট পর্যন্ত heapify কল করে পুরো অ্যারেকে ম্যাক্স হিপে বদলায়। তারপর প্রতিবার রুট (সর্বোচ্চ মান) বের করে অ্যারার শেষে নেওয়া হয় এবং বাকি হিপের আকার কমিয়ে আবার heapify কল করা হয়।
main() ফাংশন
অ্যারে প্রিন্ট করা হয়, heapSort কল করা হয়, তারপর সর্ট করা অ্যারে প্রিন্ট করা হয়।
সময় জটিলতা: O(n log n) সব ক্ষেত্রে। স্পেস জটিলতা: O(1) (ইন-প্লেস সর্টিং)।
