হিপ সোর্ট (Heap Sort) হল একটি সোর্টিং অ্যালগরিদম যা হিপ (heap) ডেটা স্ট্রাকচার ব্যবহার করে। প্রতিবার হিপের রুট এলিমেন্টটি অর্থাৎ সবচেয়ে বড় এলিমেন্টটি সরিয়ে একটি অ্যারেতে সংরক্ষণ করা হয়। সেটিকে ডানের দিয়ের পাতা এলিমেন্ট দ্বারা প্রতিস্থাপন করা হয় এবং তারপর হিপটি পুনঃস্থাপন করা হয়। এটি হিপে আর কোনো এলিমেন্ট না থাকা পর্যন্ত চলতে থাকে এবং অ্যারেটি সাজানো হয়।
উদাহরণ
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() ফাংশনে অ্যারে arr থাকে। এটি প্রাথমিক অ্যারে প্রিন্ট করে এবং তারপর heapSort() ফাংশনটি কল করে যা অ্যারেটি সাজাবে।
heapSort() ফাংশনটি প্রথমে দেওয়া এলিমেন্টগুলোকে একটি হিপে রূপান্তর করে। এটি for লুপ এবং সমস্ত নন-লিফ এলিমেন্টের জন্য heapify() ফাংশন কল করে করা হয়।
হিপ তৈরি হওয়ার পর, একটি for লুপ ব্যবহার করে হিপের রুট এলিমেন্ট অর্থাৎ সবচেয়ে বড় এলিমেন্ট সরিয়ে ফেলা হয়। সেটিকে ডানের দিয়ের পাতা এলিমেন্ট দ্বারা প্রতিস্থাপন করা হয় এবং আবার heapify() কল করা হয় হিপ পুনঃস্থাপন করার জন্য।
heapify() ফাংশনটি এলিমেন্টগুলোকে সাজিয়ে হিপ স্ট্রাকচার তৈরি করে। এই প্রক্রিয়া সূচক i-তে থাকা এলিমেন্ট থেকে শুরু হয় কারণ এটিকে heapify() ফাংশনের জন্য রুট এলিমেন্ট মনে করা হয়।
শেষে, সাজানো অ্যারেটি Main() ফাংশনে প্রদর্শন করা হয়।
