Java Technologies Java তে Heap ইমপ্লিমেন্টেশন গাইড ও নোট

Heap কি?

Heap হল একটি বিশেষ ধরনের বাইনারি ট্রী (Binary Tree) যেখানে প্রতিটি নোডের মান তার চাইল্ড নোডের মানের তুলনায় বেশি (বা কম) হয়। এটি সাধারণত দুটি ধরনের হয়ে থাকে:

• Max Heap: এখানে পিতার মান তার সমস্ত চাইল্ড নোডের মানের চেয়ে বড় বা সমান।
• Min Heap: এখানে পিতার মান তার সমস্ত চাইল্ড নোডের মানের চেয়ে ছোট বা সমান।

Heap ডেটা স্ট্রাকচারটি সাধারণত Priority Queue, Heap Sort এবং Graph algorithms (যেমন Dijkstra's shortest path) ইত্যাদির জন্য ব্যবহৃত হয়।

1. Heap এর বৈশিষ্ট্য

• Complete Binary Tree: Heap একটি পূর্ণ বাইনারি ট্রী (Complete Binary Tree), যেখানে প্রতিটি স্তরের নোড সম্পূর্ণভাবে পূর্ণ থাকে, একমাত্র শেষ স্তরে নোড কম থাকতে পারে।
• Heap Property:
  • Max Heap: পিতার মান চাইল্ড নোডের চেয়ে বড়।
  • Min Heap: পিতার মান চাইল্ড নোডের চেয়ে ছোট।

Heap সাধারণত দুটি অপারেশন খুব দ্রুত করতে সাহায্য করে:

• Insert: একটি নতুন উপাদান ইনসার্ট করা।
• Extract: সর্বোচ্চ বা সর্বনিম্ন উপাদান (Max Heap বা Min Heap অনুসারে) বের করা।

2. Heap ইমপ্লিমেন্টেশন using Array

Heap-কে Array ব্যবহার করে ইমপ্লিমেন্ট করা হয় কারণ Array এর মধ্যে পিতার ইনডেক্স এবং তার চাইল্ডদের ইনডেক্স খুব সহজে পঠনযোগ্য এবং আপডেটযোগ্য। একটি নোডের পিতার ইনডেক্স হবে i এবং তার বাম চাইল্ড হবে 2*i + 1, আর ডান চাইল্ড হবে 2*i + 2।

Heap ইমপ্লিমেন্টেশন using Max Heap:

public class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;

    // Constructor to initialize heap with capacity
    public MaxHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }

    // Method to return the index of the parent node
    private int parent(int i) {
        return (i - 1) / 2;
    }

    // Method to return the index of the left child
    private int leftChild(int i) {
        return 2 * i + 1;
    }

    // Method to return the index of the right child
    private int rightChild(int i) {
        return 2 * i + 2;
    }

    // Method to heapify the tree
    private void heapify(int i) {
        int largest = i;
        int left = leftChild(i);
        int right = rightChild(i);

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

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

        // If the largest is not the current node, swap and heapify the affected subtree
        if (largest != i) {
            swap(i, largest);
            heapify(largest);
        }
    }

    // Method to insert a new element
    public void insert(int key) {
        if (size == capacity) {
            System.out.println("Heap is full!");
            return;
        }

        // Insert the new key at the end of the heap
        heap[size] = key;
        int i = size;
        size++;

        // Fix the max-heap property if it's violated
        while (i > 0 && heap[parent(i)] < heap[i]) {
            swap(i, parent(i));
            i = parent(i);
        }
    }

    // Method to remove the root element (maximum in Max Heap)
    public int extractMax() {
        if (size <= 0) {
            System.out.println("Heap is empty");
            return Integer.MIN_VALUE;
        }

        if (size == 1) {
            size--;
            return heap[0];
        }

        // Swap the root with the last element
        int root = heap[0];
        heap[0] = heap[size - 1];
        size--;

        // Heapify the root element
        heapify(0);

        return root;
    }

    // Method to swap two elements in the heap
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // Method to display the heap
    public void display() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);

        // Inserting elements into the Max Heap
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        maxHeap.insert(30);
        maxHeap.insert(15);

        System.out.println("Max Heap:");
        maxHeap.display();  // Output: 30 20 5 10 15

        // Extracting the maximum element
        System.out.println("Extracted Max: " + maxHeap.extractMax());  // Output: 30

        System.out.println("Max Heap after extraction:");
        maxHeap.display();  // Output: 20 15 5 10
    }
}

ব্যাখ্যা:

1. insert: নতুন একটি মান কোণায় ইনসার্ট করে এবং হিপ প্রপার্টি ঠিক রাখতে heapify প্রক্রিয়া চালানো হয়।
2. extractMax: রুট নোড (সর্বোচ্চ মান) সরিয়ে ফেলা হয় এবং হিপ প্রপার্টি ঠিক করতে heapify করা হয়।
3. heapify: এটি একটি রিকার্সিভ মেথড যা একটি নির্দিষ্ট নোডের নিচে হিপ প্রপার্টি বজায় রাখে।
4. swap: দুইটি উপাদান একে অপরের স্থানে বদলে ফেলে।

3. Heap Sort Algorithm

Heap Sort একটি comparison-based sorting algorithm যা Max Heap বা Min Heap ব্যবহার করে ডেটাকে সজ্জিত করে। Heap Sort সোজাসুজি ডেটা সজ্জিত করতে সাহায্য করে এবং এটি একটি O(n log n) টাইম কমপ্লেক্সিটি প্রদান করে।

Heap Sort এর প্রক্রিয়া:

1. প্রথমে একটি Max Heap তৈরি করা হয়।
2. এরপর রুট (সর্বোচ্চ মান) বের করে তাকে সঠিক জায়গায় রেখে, অবশিষ্ট তালিকায় heapify চালানো হয়।
3. এই প্রক্রিয়া পুনরাবৃত্তি করা হয় যতক্ষণ না পুরো তালিকা সজ্জিত হয়।

উদাহরণ: Heap Sort Implementation

public class HeapSort {

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

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

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

    // Method to heapify a subtree rooted at index i
    private void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        // 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, swap and continue heapifying
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    // Method to print the array
    public void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

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

        HeapSort heapSort = new HeapSort();
        System.out.println("Unsorted array:");
        heapSort.printArray(arr);

        heapSort.heapSort(arr);

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

ব্যাখ্যা:

• heapSort: প্রথমে একটি max heap তৈরি করা হয় এবং তারপরে রুট উপাদানটি (সর্বোচ্চ মান) বের করা হয় এবং সঠিক জায়গায় রাখা হয়।
• heapify: প্রতিটি উপাদানকে তার সঠিক অবস্থানে রাখার জন্য heapify পদ্ধতি ব্যবহার করা হয়।
• printArray: সজ্জিত অ্যারের উপাদানগুলি প্রিন্ট করা হয়।

সারাংশ

Heap হল একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা সাধারণত Priority Queue, Heap Sort এবং Graph Algorithms এর জন্য ব্যবহৃত হয়। এটি দুটি প্রধান ধরনের হতে পারে:

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

Heap ইমপ্লিমেন্টেশন করতে সাধারণত Array বা Linked List ব্যবহার করা হয়, তবে Array-based heap অধিকাংশ সময় ব্যবহার করা হয় কারণ এটি খুবই কার্যকরী। Heap Sort একটি গুরুত্বপূর্ণ অ্যালগরিদম যা Heap ব্যবহার করে দ্রুত এবং কার্যকরভাবে ডেটা সজ্জিত করতে সাহায্য করে।