হিপ সর্ট অ্যালগরিদম ব্যবহার করে 10টি উপাদানের একটি অ্যারে সাজানোর জন্য C++ প্রোগ্রাম

হিপ সর্ট বাইনারি হিপ ডেটা স্ট্রাকচারের উপর ভিত্তি করে। বাইনারি হিপে একটি প্যারেন্ট নোডের চাইল্ড নোডগুলি সর্বাধিক হিপের ক্ষেত্রে এটির থেকে ছোট বা সমান, এবং একটি মিন হিপের ক্ষেত্রে একটি প্যারেন্ট নোডের চাইল্ড নোডগুলি এর থেকে বড় বা সমান৷

একটি উদাহরণ যা হিপ সাজানোর সমস্ত ধাপ ব্যাখ্যা করে তা নিম্নরূপ।

সাজানোর আগে 10টি উপাদান সহ মূল অ্যারে হল −

এই অ্যারেটি max-heapify ব্যবহার করে একটি বাইনারি সর্বোচ্চ হিপে তৈরি করা হয়েছে। একটি অ্যারে হিসাবে উপস্থাপিত এই সর্বোচ্চ হিপটি নিম্নরূপ দেওয়া হয়েছে।

সর্বাধিক হিপের মূল উপাদানটি বের করা হয় এবং অ্যারের শেষে স্থাপন করা হয়। তারপর max heapify বলা হয় বাকি উপাদানগুলিকে একটি max হিপে রূপান্তর করতে। এটি করা হয় যতক্ষণ না শেষ পর্যন্ত সাজানো অ্যারে প্রাপ্ত হয় যা নিম্নরূপ দেওয়া হয় -

হিপ সর্ট অ্যালগরিদম ব্যবহার করে 10টি উপাদানের অ্যারে সাজানোর প্রোগ্রামটি নিম্নরূপ দেওয়া হয়েছে।

উদাহরণ

#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;
   for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);
   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;
i   nt i;
   cout<<"Given array is: "<<endl;
   for (i = 0; i *lt; n; i++)
   cout<<arr[i]<<" ";
   cout<<endl;
   heapSort(arr, n);
   printf("\nSorted array is: \n");
   for (i = 0; i < n; ++i)
   cout<<arr[i]<<" ";
}

আউটপুট

Given array is:
20 7 1 54 10 15 90 23 77 25
Sorted array is:
1 7 10 15 20 23 25 54 77 90

উপরের প্রোগ্রামে, heapify() ফাংশনটি উপাদানগুলিকে একটি হিপে রূপান্তর করতে ব্যবহৃত হয়। এই ফাংশনটি একটি পুনরাবৃত্ত ফাংশন এবং এটি একটি সর্বাধিক হিপ তৈরি করে যা এলিমেন্ট থেকে শুরু করে এটিকে বলা হয় এই ক্ষেত্রে i. এটি প্রদর্শনকারী কোড স্নিপেটটি নিম্নরূপ দেওয়া হয়েছে।

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);
   }
}

heapSort() ফাংশন হিপ সর্ট ব্যবহার করে অ্যারের উপাদানগুলিকে সাজায়। এটি নন-লিফ নোড থেকে শুরু হয় এবং তাদের প্রতিটিতে heapify() কল করে। এটি অ্যারেটিকে একটি বাইনারি সর্বোচ্চ হিপে রূপান্তর করে। এটি নিম্নরূপ দেখানো হয়েছে -

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

এর পরে, ফাংশন heapSort() ফর লুপের প্রতিটি পুনরাবৃত্তিতে রুট এলিমেন্ট নেয় এবং এটিকে অ্যারের শেষে রাখে। তারপর heapify() বলা হয় নিশ্চিত করার জন্য যে বাকি উপাদানগুলি একটি সর্বোচ্চ হিপ। অবশেষে, এই পদ্ধতিটি ব্যবহার করে সমস্ত উপাদান সর্বাধিক হিপ থেকে বের করা হয় এবং একটি সাজানো অ্যারে পাওয়া যায়। এটি নিম্নরূপ দেখানো হয়েছে।

for (int i = n - 1; i >= 0; i--) {
   temp = arr[0];
   arr[0] = arr[i];
   arr[i] = temp;
   heapify(arr, i, 0);
}

ফাংশন main(), প্রথমে অ্যারে প্রদর্শিত হয়। তারপর, ফাংশন heapSort() অ্যারে সাজানোর জন্য বলা হয়। এটি নিম্নলিখিত কোড স্নিপেট দ্বারা দেওয়া হয়৷

cout<<"Given array is: "<<endl;
for (i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);

অবশেষে, সাজানো অ্যারে প্রদর্শিত হয়। এটি নীচে দেখানো হয়েছে৷

printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";