Computer Programming Heapsort Algorithm এর প্রয়োগ গাইড ও নোট

Heapsort Algorithm এর প্রয়োগ

Heapsort একটি তুলনামূলক সোর্টিং অ্যালগরিদম যা Max-Heap বা Min-Heap ডেটা স্ট্রাকচার ব্যবহার করে একটি অ্যারে সজ্জিত করে। এটি একটি O(n log n) সময় জটিলতা সহ কাজ করে, যা কার্যকর এবং দক্ষ সোর্টিং অ্যালগরিদম হিসেবে পরিচিত। Heapsort দুইটি প্রধান অংশে বিভক্ত:

1. হিপ তৈরি (Building the heap): প্রথমে একটি হিপ তৈরি করা হয় (সাধারণত Max-Heap বা Min-Heap)।
2. হিপ এক্সট্র্যাকশন (Heap extraction): রুট (সর্বোচ্চ বা সর্বনিম্ন) উপাদানটি মুছে ফেলা হয় এবং হিপের কাঠামো ঠিক রাখতে হিপিফাই করা হয়।

এটি একটি অস্থির সোর্টিং অ্যালগরিদম (in-place sorting algorithm), অর্থাৎ এটি অতিরিক্ত মেমরি ব্যবহারের প্রয়োজন হয় না এবং অ্যারের উপর সরাসরি কাজ করে।

Heapsort Algorithm এর ধাপ

1. Max-Heap তৈরি করা: অ্যারের সব উপাদানকে Max-Heap গঠনের মাধ্যমে সাজানো হয়, যাতে সর্বোচ্চ উপাদান রুটে চলে আসে।
2. এক্সট্র্যাকশন: সর্বোচ্চ উপাদান (রুট) মুছে ফেলা হয় এবং তাকে অ্যারের শেষ পজিশনে স্থাপন করা হয়। তারপর হিপের গঠন ঠিক রাখতে heapify অপারেশন চালানো হয়।
3. ধাপ ২ পুনরাবৃত্তি: একে একে সকল উপাদানকে রুট থেকে মুছে ফেলা হয় এবং সঠিক অবস্থানে স্থাপন করা হয় যতক্ষণ না হিপটি শূন্য হয়।

Heapsort এর সি প্রোগ্রামিং ভাষায় ইমপ্লিমেন্টেশন

#include <stdio.h>

#define MAX 10

int heap[MAX];
int size = 0;

// Swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify the tree to maintain Max-Heap property
void heapify(int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    // Left child is larger
    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }

    // Right child is larger
    if (right < size && heap[right] > heap[largest]) {
        largest = right;
    }

    // If largest is not root
    if (largest != i) {
        swap(&heap[i], &heap[largest]);
        heapify(largest);
    }
}

// Build the heap (Max-Heap)
void buildHeap() {
    // Start from the last non-leaf node and heapify the tree
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(i);
    }
}

// Heapsort function
void heapsort() {
    buildHeap(); // Build Max-Heap
    
    for (int i = size - 1; i >= 1; i--) {
        // Swap root (max element) with the last element
        swap(&heap[0], &heap[i]);
        
        // Reduce heap size by 1
        size--;
        
        // Heapify the root element to restore Max-Heap property
        heapify(0);
    }
}

// Print the heap array
void printHeap() {
    for (int i = 0; i < size; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");
}

int main() {
    // Input array for heapsort
    heap[0] = 40;
    heap[1] = 20;
    heap[2] = 30;
    heap[3] = 10;
    heap[4] = 50;
    heap[5] = 70;
    heap[6] = 60;
    size = 7;

    printf("Original Array: ");
    printHeap();

    heapsort();

    printf("Sorted Array: ");
    printHeap();

    return 0;
}

Heapsort এর স্টেপ-বাই-স্টেপ কাজ

1. Max-Heap গঠন করা:
   • প্রথমে অ্যারের সব উপাদানকে Max-Heap এর কাঠামোয় সাজানো হয়।
   • হিপিফাই ফাংশন প্রতিটি নোডের জন্য কাজ করে, যাতে প্রতিটি নোড তার সন্তানের মানের তুলনায় বড় থাকে।
2. এক্সট্র্যাকশন এবং সঠিক অবস্থানে স্থাপন:
   • হিপের রুট (সর্বোচ্চ মান) সর্বশেষ উপাদানের সাথে এক্সচেঞ্জ করা হয় এবং তারপর heapify ফাংশন পুনরায় চালানো হয় যাতে হিপের কাঠামো ঠিক থাকে।
   • এভাবে প্রতিটি উপাদান একে একে সঠিক স্থানে স্থানান্তরিত হয়।

3. এটি O(n log n) সময়ে কাজ করে:

   • প্রথম ধাপ (Max-Heap গঠন) O(n) সময় নেয়, কারণ হিপিফাই অপারেশন প্রতিটি স্তরের জন্য O(log n) সময় নেয় এবং মোট nটি উপাদান প্রক্রিয়া করা হয়।
   • দ্বিতীয় ধাপ (এক্সট্র্যাকশন) প্রতি উপাদানের জন্য O(log n) সময় নেয়, যেহেতু heapify প্রতিটি এক্সট্র্যাকশনের পরে একবার করা হয়।

   তাই Heapsort এর মোট সময় জটিলতা হয় **O(n log n)**।

Heapsort এর সুবিধা এবং অসুবিধা

সুবিধা:

• স্থির সাইজ (In-place): Heapsort অতিরিক্ত মেমরি ব্যবহার করে না।
• সময় জটিলতা (Time Complexity): Heapsort O(n log n) সময় জটিলতায় কাজ করে, যা অন্যান্য সোজা সোর্টিং অ্যালগরিদমের চেয়ে ভালো।
• এক্সট্রা মেমরি প্রয়োজন নয়: এটি অন্যান্য সোর্টিং অ্যালগরিদমের মতো অতিরিক্ত মেমরি খরচ করে না।

অসুবিধা:

• স্থিতিস্থাপকতা (Stability): Heapsort একটি অস্থির (unstable) সোর্টিং অ্যালগরিদম, অর্থাৎ সমান মানের উপাদানদের আদান-প্রদান নিশ্চিত করা হয় না।
• প্রয়োগ সহজ নয়: অন্যান্য সোজা সোর্টিং অ্যালগরিদমের তুলনায় Heapsort প্রোগ্রামিংয়ে একটু কঠিন হতে পারে।

সারসংক্ষেপ

Heapsort একটি শক্তিশালী এবং কার্যকর সোর্টিং অ্যালগরিদম যা Max-Heap ডেটা স্ট্রাকচার ব্যবহার করে কাজ করে। এটি O(n log n) সময়ে কাজ করে এবং ইন-প্লেস সোর্টিং প্রদান করে, তবে এটি অস্থির (unstable) সোর্টিং অ্যালগরিদম। Heapsort বিভিন্ন প্রোগ্রামিং অ্যাপ্লিকেশন যেমন গ্রাফ অ্যালগরিদম, সিস্টেম সিডিউলিং, এবং অন্যান্য কাজের জন্য ব্যবহৃত হয়।