Heap Sort Algorithm

Heap Sort একটি comparison-based sorting algorithm যা binary heap ডাটা স্ট্রাকচার ব্যবহার করে। এটি একটি in-place অ্যালগরিদম, অর্থাৎ এটি অতিরিক্ত স্পেস ব্যবহার না করে অ্যারে বা লিস্টের মধ্যে সরাসরি সাজানো কাজটি করে। Heap Sort অ্যালগরিদমের সময় জটিলতা হল O(n log n), যা সর্বাধিক efficient সোর্টিং অ্যালগরিদমগুলোর মধ্যে একটি।

1. Heap Data Structure

Heap একটি পূর্ণ বাইনারি ট্রি (Complete Binary Tree) যেখানে প্রতিটি নোড তার সন্তানের চেয়ে বড় (max heap) বা ছোট (min heap) থাকে। এটি দুটি ধরনের হতে পারে:

1. Max Heap: প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের মানের চেয়ে বড় বা সমান।
2. Min Heap: প্রতিটি প্যারেন্ট নোডের মান তার সন্তানের মানের চেয়ে ছোট বা সমান।

Heap-এর মৌলিক বৈশিষ্ট্যগুলি হল:

• Complete Binary Tree: এটি একটি পূর্ণ বাইনারি ট্রি যেখানে প্রতিটি স্তরের সব নোড পূর্ণ থাকে, একমাত্র শেষ স্তরের নোডগুলি বাম থেকে ডানে পূর্ণ হতে পারে।
• Max-Heap এবং Min-Heap: এই দুটি ধরণের heaps অনুযায়ী সাজানো হয়।

2. Heap Sort Algorithm

Heap Sort দুটি ধাপে কাজ করে:

1. Build a max-heap: প্রথমে সম্পূর্ণ অ্যারে থেকে একটি max heap তৈরি করা হয়। অর্থাৎ, অ্যারের প্রথম উপাদানটি (root) সব থেকে বড় হবে।
2. Extract max (root) and heapify: তারপর, root (সবচেয়ে বড় উপাদান) বের করে অ্যারের শেষ উপাদানের সাথে প্রতিস্থাপন করা হয় এবং তারপর heapify প্রক্রিয়া চালানো হয় যাতে গাছটি আবার max heap হয়ে যায়। এই প্রক্রিয়াটি পুনরাবৃত্তি করা হয় যতক্ষণ না সমস্ত উপাদান সঠিকভাবে সজ্জিত হয়।

2.1. Heapify Process

Heapify হলো একটি প্রক্রিয়া যা একটি সুনির্দিষ্ট নোডকে তার সঠিক অবস্থানে নিয়ে আসে, যাতে heap property বজায় থাকে। এটি একটি পুনরাবৃত্তি পদ্ধতি, যেখানে একটি নোড তার সন্তানের সাথে জায়গা পরিবর্তন করে যতক্ষণ না গাছটি সঠিকভাবে সাজানো হয়।

3. Heap Sort Algorithm Steps

1. Build Max-Heap: প্রথমে একটি Max-Heap তৈরি করুন, যেখানে সবচেয়ে বড় উপাদানটি গাছের শীর্ষে থাকবে।
2. Extract the Maximum: গাছের শীর্ষে থাকা সর্বোচ্চ উপাদানটি বের করে শেষ উপাদানের সাথে স্বাপস করুন।
3. Heapify: গাছের গঠন সঠিক রাখতে heapify প্রক্রিয়া চালান।
4. পুনরাবৃত্তি করুন যখন পর্যন্ত গাছের সব উপাদান সঠিকভাবে সাজানো না হয়।

4. Heap Sort in Java

public class HeapSort {

    // Function to perform heap sort
    public void heapSort(int[] arr) {
        int n = arr.length;

        // Build a max-heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // Extract elements one by one from the heap
        for (int i = n - 1; i > 0; i--) {
            // Swap the current root with the last element
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Call heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    // Function to maintain the heap property
    private void heapify(int[] arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int left = 2 * i + 1; // Left child
        int right = 2 * i + 2; // Right child

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    // Utility function to print an array
    public void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        HeapSort hs = new HeapSort();

        System.out.println("Original Array:");
        hs.printArray(arr);

        hs.heapSort(arr);

        System.out.println("Sorted Array:");
        hs.printArray(arr); // Output: 5 6 7 11 12 13
    }
}

4.1. Explanation of Code:

1. heapSort: মূল হিপ সোর্ট ফাংশন যেখানে প্রথমে max-heap তৈরি করা হয় এবং তারপর প্রতিটি উপাদান বের করে তাকে সঠিকভাবে পুনরায় হিপ গঠন করতে বলা হয়।
2. heapify: এটি একটি সহায়ক ফাংশন যা গাছের কোনো নোডের জন্য heap property বজায় রাখে। এটি প্রতিটি নোডের সন্তানদের সাথে তুলনা করে এবং প্রয়োজনে তাদের মধ্যে স্থানান্তর করে।
3. printArray: এটি একটি সহজ ফাংশন যা অ্যারের উপাদানগুলো কনসোল এ প্রদর্শন করে।

5. Time Complexity of Heap Sort

• Build Max-Heap: O(n) where n is the number of elements in the array.
• Heapify: Each heapify operation takes O(log n), and since we call it for every element, the time complexity for this part is O(n log n).
• Therefore, the overall time complexity of Heap Sort is O(n log n) for both average and worst-case scenarios.

6. Space Complexity of Heap Sort

Heap Sort is an in-place sorting algorithm, meaning it does not require extra space apart from the input array. Therefore, its space complexity is O(1).

7. Advantages of Heap Sort

1. Time Complexity: Heap sort guarantees an optimal time complexity of O(n log n), which is the same as other efficient sorting algorithms like merge sort and quick sort.
2. In-place Sorting: Heap sort does not require additional storage apart from the input array, making it more space-efficient than other algorithms like merge sort.
3. No Worst-Case Scenario: Unlike quicksort, which can degrade to O(n²) in the worst case, heap sort guarantees O(n log n) time complexity.

8. Disadvantages of Heap Sort

1. Not Stable: Heap sort is not stable (i.e., it does not preserve the relative order of equal elements).
2. Less Cache-Friendly: Heap sort is less cache-efficient compared to algorithms like quicksort because it involves random access to elements in the array, which can result in more cache misses.

সারাংশ

Heap Sort হল একটি comparison-based in-place sorting algorithm যা max-heap বা min-heap ডাটা স্ট্রাকচার ব্যবহার করে। এটি O(n log n) টাইম কমপ্লেক্সিটি সহ কার্যকরভাবে কাজ করে এবং ইনপুট অ্যারেতে সরাসরি ডাটা সাজায়। Heapify এবং rotation এর মাধ্যমে গাছের গঠন সঠিক রাখে এবং সঠিকভাবে ডাটা সাজানো হয়।

Heap Sort এর বিভিন্ন সুবিধা রয়েছে, তবে এটি stable নয় এবং cache efficiency কিছুটা কম। তবে এর time complexity এবং space efficiency অনেক ক্ষেত্রে এটি একটি শক্তিশালী অ্যালগরিদম হিসেবে প্রমাণিত হয়েছে।