হিপ সোর্ট (Heap Sort)

হিপ সোর্ট হিপ ডেটা স্ট্রাকচার উপরে কাজ করে। হিপ একটি কমপ্লিট বাইনারি ট্রি। দুটি ধরনের হিপ থাকে: মিন-হিপ (রুট মিনিমাম) এবং ম্যাক্স-হিপ (রুট ম্যাক্সিমাম)। হিপ ফর্ম করার পর রুট থেকে এলিমেন্ট ডিলিট করে লাস্ট এলিমেন্টকে রুটে আনা হয়, তারপর রি-হিপ করা হয়। এই প্রক্রিয়ায় পুরো অ্যারে সর্ট হয়।

হিপ সোর্টের জটিলতা

• টাইম কমপ্লেক্সিটি: 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(array, size) - ম্যাক্স হিপ তৈরি করে

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

heapSort(array, size)

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

C++ উদাহরণ

#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) {
    for(int i = 1; i <= n; i++) {
        int node = i, par = node/2;
        while(par >= 1) {
            if(array[par] < array[node]) swap(array[par], array[node]);
            node = par; par = node/2;
        }
    }
}

void heapSort(int *array, int n) {
    for(int i = n; i >= 1; i--) {
        heapify(array, i);
        swap(array[1], array[i]);
    }
}

int main() {
    int n; cout << "Enter the number of elements: "; cin >> n;
    int arr[n+1]; // 1-based indexing
    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