Heap Sort হল একটি সাজানোর অ্যালগরিদম যা হিপ ডেটা স্ট্রাকচার ব্যবহার করে। প্রতিবার হিপের মূল উপাদান অর্থাৎ সবচেয়ে বড় উপাদানটি সরিয়ে একটি অ্যারেতে সংরক্ষণ করা হয়। এটি ডানদিকের পাতার উপাদান দ্বারা প্রতিস্থাপিত হয় এবং তারপর স্তূপটি পুনঃস্থাপিত হয়। এটি করা হয় যতক্ষণ না হিপে আর কোনো উপাদান অবশিষ্ট থাকে না এবং অ্যারে সাজানো হয়।
একটি প্রোগ্রাম যা C# এ হিপ সাজানোর প্রদর্শন করে তা নিম্নরূপ দেওয়া হল।
উদাহরণ
using System;
namespace HeapSortDemo {
public class example {
static void heapSort(int[] arr, int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
public static void Main() {
int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
heapSort(arr, 10);
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
}
}
} আউটপুট
উপরের প্রোগ্রামের আউটপুট নিম্নরূপ।
Heap Sort Initial array is: 55 25 89 34 12 19 78 95 1 100 Sorted Array is: 1 12 19 25 34 55 78 89 95 100
এখন, আসুন আমরা উপরের প্রোগ্রামটি বুঝতে পারি।
ফাংশন main() অ্যারে অ্যারে ধারণ করে। এটি প্রাথমিক অ্যারে প্রিন্ট করে এবং তারপরে heapSort() ফাংশনটিকে কল করে যা অ্যারেটি সাজাতে হবে। এটি নিম্নলিখিত কোড স্নিপেটে দেখা যেতে পারে।
int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
}
heapSort(arr, 10); ফাংশন heapSort() প্রথমে প্রদত্ত উপাদানগুলিকে একটি হিপে রূপান্তর করে। এটি for loop ব্যবহার করে এবং heapify() ফাংশনটিকে কল করে হিপের সমস্ত নন-লিফ উপাদানগুলির জন্য করা হয়। এটি নিম্নলিখিত কোড স্নিপেটে দেখা যেতে পারে।
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
হিপ তৈরি হওয়ার পর, হিপের রুট এলিমেন্ট অর্থাৎ সবচেয়ে বড় এলিমেন্ট অপসারণ করতে a for loop ব্যবহার করা হয়। এটি ডানদিকের পাতার উপাদান দ্বারা প্রতিস্থাপিত হয় এবং তারপর heapify() কে আবার কল করা হয় হিপটি পুনরায় স্থাপন করতে। এটি নিম্নলিখিত কোড স্নিপেটে দেখা যেতে পারে।
for (int i = n-1; i>=0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
} ফাংশন heapify() প্রয়োজনীয় উপাদানগুলিকে সাজিয়ে একটি হিপ গঠন তৈরি করে। এই প্রক্রিয়াটি ইনডেক্স i-এর এলিমেন্ট থেকে শুরু হয় যার জন্য heapify() ফাংশনের রুট এলিমেন্ট হিসেবে বিবেচিত হয়। এটি নিম্নলিখিত কোড স্নিপেটে দেখা যেতে পারে।
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
} অবশেষে, সাজানো অ্যারে প্রধান() ফাংশনে প্রদর্শিত হয়। এটি নিম্নলিখিত কোড স্নিপেটে দেখা যেতে পারে।
Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
Console.Write(arr[i] + " ");
} 