গাদা সাজানোর

হিপ ডেটা স্ট্রাকচারে হিপ সাজানো হয়। আমরা জানি যে গাদা একটি সম্পূর্ণ বাইনারি গাছ। গাদা গাছ দুই ধরনের হতে পারে। মিন-হিপ বা সর্বোচ্চ হিপ। মিন হিপের জন্য মূল উপাদানটি সর্বনিম্ন এবং সর্বাধিক হিপের জন্য রুটটি সর্বাধিক। একটি গাদা গঠন করার পর, আমরা রুট থেকে একটি উপাদান মুছে ফেলতে পারি এবং শেষ উপাদানটিকে রুটে পাঠাতে পারি। এই অদলবদল পদ্ধতির পরে, আমাদের পুরো অ্যারেটি পুনরায় হিপ করতে হবে। রুট থেকে উপাদান মুছে ফেলার মাধ্যমে আমরা পুরো অ্যারে সাজাতে পারি।

হিপ সাজানোর কৌশলের জটিলতা

• সময়ের জটিলতা: O(n log n)
• স্পেস জটিলতা: O(1)

ইনপুট এবং আউটপুট

Input:
A list of unsorted data: 30 8 99 11 24 39
Output:
Array before Sorting: 30 8 99 11 24 39
Array after Sorting: 8 11 24 30 39 99

অ্যালগরিদম

heapify (অ্যারে, আকার)

ইনপুট - ডেটার একটি অ্যারে, এবং অ্যারের মোট সংখ্যা

আউটপুট - একটি অ্যারে উপাদান ব্যবহার করে সর্বাধিক হিপ

Begin
   for i := 1 to size do
      node := i
      par := floor (node / 2)
      while par >= 1 do
         if array[par] < array[node] then
            swap array[par] with array[node]
         node := par
         par := floor (node / 2)
      done
   done
End

heapSort(অ্যারে, আকার)

ইনপুট: ডেটার একটি অ্যারে, এবং অ্যারের মোট সংখ্যা

আউটপুট −nbsp; সাজানো অ্যারে

Begin
   for i := n to 1 decrease by 1 do
      heapify(array, i)
      swap array[1] with array[i]
   done
End

উদাহরণ

#include<iostream>
using namespace std;

void display(int *array, int size) {
   for(int i = 1; i<=size; i++)
      cout << array[i] << " ";
   cout << endl;
}

void heapify(int *array, int n) {
   int i, par, l, r, node;
   // create max heap

   for(i = 1; i<= n; i++) {
      node = i; par = (int)node/2;
      while(par >= 1) {
         //if new node bigger than parent, then swap
         if(array[par] < array[node])
            swap(array[par], array[node]);
         node = par;
         par = (int)node/2;//update parent to check
      }
   }
}

void heapSort(int *array, int n) {
   int i;

   for(i = n; i>= 1; i--) {
      heapify(array, i);//heapify each time
      swap(array[1], array[i]);//swap last element with first
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n+1]; //effective index starts from i = 1.
   cout << "Enter elements:" << endl;

   for(int i = 1; i<=n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   heapSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

আউটপুট

Enter the number of elements: 6
Enter elements:
30 8 99 11 24 39
Array before Sorting: 30 8 99 11 24 39
Array after Sorting: 8 11 24 30 39 99