হিপ (Heap) গাইড ও নোট

হিপ (Heap) একটি বিশেষ ধরনের বাইনারি ট্রি ডাটা স্ট্রাকচার, যা নির্দিষ্ট কিছু নিয়ম অনুসরণ করে ডাটা সংরক্ষণ করে। এটি একটি সম্পূর্ণ বাইনারি ট্রি (Complete Binary Tree), এবং এর প্রধান বৈশিষ্ট্য হল, প্রতিটি প্যারেন্ট নোড তার চাইল্ড নোডের চেয়ে বড় (বা ছোট) হয়। এই বৈশিষ্ট্যের জন্য হিপ খুবই কার্যকরী ডাটা স্ট্রাকচার, বিশেষ করে প্রায়োরিটি কিউ (Priority Queue), হিপ সাজানো (Heap Sort) ইত্যাদির জন্য।

হিপ সাধারণত দুটি ধরনের হয়:

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

হিপের প্রধান অপারেশনগুলি হল:

• insert(): একটি নতুন উপাদান হিপে যোগ করা।
• extract(): সর্বোচ্চ (ম্যাক্স হিপে) বা সর্বনিম্ন (মিন হিপে) উপাদান মুছে ফেলা।
• peek(): হিপের শীর্ষ উপাদান দেখা, কিন্তু মুছে ফেলা হয় না।
• heapify(): হিপ বৈশিষ্ট্য বজায় রেখে একটি সাবট্রি বা পুরো ট্রি সাজানো।

হিপ ইমপ্লিমেন্টেশন (Max Heap) জাভাতে

এখানে, একটি ম্যাক্স হিপ ইমপ্লিমেন্ট করা হবে, যা একটি সম্পূর্ণ বাইনারি ট্রি ব্যবহার করে তৈরি করা হবে।

1. হিপ ক্লাস (Heap Class)

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

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

    // Parent index calculation
    private int parent(int index) {
        return (index - 1) / 2;
    }

    // Left child index calculation
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    // Right child index calculation
    private int rightChild(int index) {
        return 2 * index + 2;
    }

    // Check if the current node is a leaf node
    private boolean isLeaf(int index) {
        return index >= size / 2 && index < size;
    }

    // Swap two elements in the heap
    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

    // Heapify the subtree rooted at index i
    private void heapify(int index) {
        if (isLeaf(index)) {
            return;
        }

        int left = leftChild(index);
        int right = rightChild(index);

        int largest = index;

        // Find the largest among the root, left child, and right child
        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }

        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }

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

    // Insert a new element into the heap
    public void insert(int element) {
        if (size == capacity) {
            System.out.println("Heap is full");
            return;
        }

        // Insert the element at the end of the heap
        heap[size] = element;
        size++;

        // Heapify the heap from bottom to top to maintain the max-heap property
        int current = size - 1;
        while (current > 0 && heap[parent(current)] < heap[current]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    // Extract the maximum element (root) from the heap
    public int extractMax() {
        if (size == 0) {
            System.out.println("Heap is empty");
            return Integer.MIN_VALUE;
        }

        // The root of the heap contains the maximum element
        int root = heap[0];

        // Move the last element to the root
        heap[0] = heap[size - 1];
        size--;

        // Heapify the root to maintain the max-heap property
        heapify(0);

        return root;
    }

    // Peek the maximum element (root) without removing it
    public int peek() {
        if (size == 0) {
            System.out.println("Heap is empty");
            return Integer.MIN_VALUE;
        }
        return heap[0];
    }

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

ক্লাসের ব্যাখ্যা:

1. insert(int element): এটি একটি নতুন উপাদান হিপে যোগ করে এবং হিপের গঠন বজায় রাখতে নিচ থেকে উপরে (bottom-up) হিপিফাই (heapify) করে।
2. extractMax(): হিপের সর্বোচ্চ উপাদান (রুট নোড) মুছে ফেলে এবং হিপের গঠন বজায় রাখতে উপরের নোড থেকে নিচে (top-down) হিপিফাই করে।
3. peek(): হিপের সর্বোচ্চ উপাদান দেখায়, তবে তা মুছে ফেলে না।
4. heapify(int index): নির্দিষ্ট নোড থেকে শুরু করে হিপ বৈশিষ্ট্য বজায় রেখে সঠিক অবস্থানে নোডটি পুনঃস্থাপন করে।
5. swap(int index1, int index2): দুটি উপাদানের মান স্ব্যাপ করে।

হিপ ব্যবহার উদাহরণ

এখন আমরা একটি ম্যাক্স হিপ তৈরি করবো এবং এর বিভিন্ন অপারেশন পরীক্ষা করবো:

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

        // Insert elements into the heap
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(15);
        maxHeap.insert(30);
        maxHeap.insert(40);
        maxHeap.insert(50);
        maxHeap.insert(100);

        // Print the heap
        System.out.println("Max Heap:");
        maxHeap.printHeap();  // Output: 100 40 50 30 10 20 15

        // Peek the maximum element
        System.out.println("Max element: " + maxHeap.peek());  // Output: 100

        // Extract the maximum element
        System.out.println("Extracted max: " + maxHeap.extractMax());  // Output: 100

        // Print the heap after extraction
        System.out.println("Heap after extraction:");
        maxHeap.printHeap();  // Output: 50 40 15 30 10 20
    }
}

আউটপুট:

Max Heap:
100 40 50 30 10 20 15
Max element: 100
Extracted max: 100
Heap after extraction:
50 40 15 30 10 20

সারাংশ

হিপ (Heap) একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার, যা ম্যাক্স হিপ (Max Heap) এবং মিন হিপ (Min Heap) হিসাবে বিভক্ত। এটি একটি সম্পূর্ণ বাইনারি ট্রি যা নির্দিষ্ট গঠন অনুসরণ করে, যেমন প্যারেন্ট নোডের মান চাইল্ড নোডের মানের চেয়ে বড় বা ছোট। জাভাতে হিপ ইমপ্লিমেন্ট করার জন্য, অ্যারে ব্যবহার করা হয়েছে এবং বিভিন্ন অপারেশন যেমন ইনসার্ট, এক্সট্র্যাক্ট, পিক এবং হিপিফাই করা হয়েছে। হিপ ব্যবহার করে হিপ সাজানো (Heap Sort), প্রায়োরিটি কিউ (Priority Queue) ইত্যাদি অপারেশন কার্যকরভাবে করা যায়।

Heap হল একটি বিশেষ ধরনের Binary Tree যা একটি নির্দিষ্ট আদেশ (order) বা নিয়ম অনুসরণ করে, যাতে পিতার (parent) মান তার সন্তানের (children) মানের সাথে সম্পর্কিত থাকে। Heap সাধারণত Priority Queue বাস্তবায়নে ব্যবহৃত হয় এবং এটি একটি complete binary tree।

Heap একটি বিশেষ ধরনের Binary Tree যা Min-Heap বা Max-Heap হতে পারে। এই স্ট্রাকচারটির দুটি প্রধান প্রকারভেদ রয়েছে:

• Min-Heap
• Max-Heap

Heap এর মধ্যে Insertion, Deletion, এবং Peek অপারেশনগুলি O(log n) সময়ে সম্পন্ন করা যায়, যা এটিকে অন্যান্য ডাটা স্ট্রাকচারের তুলনায় দ্রুত এবং কার্যকরী করে তোলে।

1. Heap এর মৌলিক ধারণা

Heap হল একটি complete binary tree, যেখানে প্রতিটি নোডের মান তার সন্তানের তুলনায় কম বা বেশি থাকে (এটা নির্ভর করে Min-Heap বা Max-Heap এর উপর)। Heap এ সাধারণত দুটি মৌলিক অপারেশন থাকে:

• Insert (Enqueue): একটি নতুন এলিমেন্ট যোগ করা।
• Extract (Dequeue): Root (সর্বোচ্চ বা সর্বনিম্ন) এলিমেন্ট মুছে ফেলা।

Heap এর অন্যতম বড় সুবিধা হল এর অপারেশনগুলি যেমন insert, delete, এবং peek দ্রুত (O(log n)) সময়ে সম্পন্ন করা সম্ভব।

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

• Complete Binary Tree: একটি complete binary tree হলো এমন একটি বাইনারি ট্রী, যেখানে সর্বশেষ স্তরের নোড ছাড়া সব স্তরে পূর্ণসংখ্যক নোড থাকে।
• Heap Property:
  • Min-Heap: প্রতিটি পিতার মান তার সন্তানের তুলনায় ছোট বা সমান হয়।
  • Max-Heap: প্রতিটি পিতার মান তার সন্তানের তুলনায় বড় বা সমান হয়।

2. Min-Heap

Min-Heap হল এমন একটি binary tree যেখানে প্রতিটি পিতার মান তার সন্তানের মানের তুলনায় ছোট বা সমান হয়। এর ফলে, Root Node সবসময় সর্বনিম্ন মান ধারণ করে থাকে।

Min-Heap এর বৈশিষ্ট্য:

• পিতার মান তার সন্তানদের তুলনায় ছোট বা সমান হবে।
• Root নোডের মান সর্বনিম্ন থাকবে।
• Min-Heap এর প্রধান ব্যবহার হল Priority Queue যেখানে সর্বনিম্ন প্রাধান্য (priority) পাওয়া উপাদানটি দ্রুত পাওয়া যায়।

উদাহরণ (Min-Heap):

           10
          /  \
        20    30
       /  \
     40    50

Min-Heap এর অপারেশন:

1. Insert: নতুন এলিমেন্ট যোগ করা।
2. Extract-Min: Root (সর্বনিম্ন) এলিমেন্ট মুছে ফেলা।
3. Peek: Root নোডের মান দেখা।

3. Max-Heap

Max-Heap হল একটি binary tree যেখানে প্রতিটি পিতার মান তার সন্তানের মানের তুলনায় বড় বা সমান হয়। এর ফলে, Root Node সবসময় সর্বাধিক মান ধারণ করে থাকে।

Max-Heap এর বৈশিষ্ট্য:

• পিতার মান তার সন্তানদের তুলনায় বড় বা সমান হবে।
• Root নোডের মান সর্বাধিক থাকবে।
• Max-Heap এর প্রধান ব্যবহার হল Priority Queue যেখানে সর্বাধিক প্রাধান্য (priority) পাওয়া উপাদানটি দ্রুত পাওয়া যায়।

উদাহরণ (Max-Heap):

           50
          /  \
        30    40
       /  \
     20    10

Max-Heap এর অপারেশন:

1. Insert: নতুন এলিমেন্ট যোগ করা।
2. Extract-Max: Root (সর্বাধিক) এলিমেন্ট মুছে ফেলা।
3. Peek: Root নোডের মান দেখা।

4. Heap এর কার্যকারিতা (Time Complexity)

Heap ডাটা স্ট্রাকচারে কিছু সাধারণ অপারেশন এবং তাদের কার্যকারিতা:

1. Insert (Enqueue): O(log n)
2. Extract (Dequeue): O(log n)
3. Peek: O(1)
4. Build Heap: O(n)

Heap ডাটা স্ট্রাকচারটি O(log n) সময়ে ইনসার্ট, ডিলিট, এবং রিইন্টারনালাইজ অপারেশন করতে সক্ষম, যা অন্যান্য স্ট্রাকচারের তুলনায় অধিক কার্যকরী।

5. Heap এর ব্যবহার

Heap বিভিন্ন ধরনের সমস্যা সমাধানে ব্যবহৃত হয়, যেমন:

1. Priority Queue: Heap এর মাধ্যমে আপনি প্রাধান্য অনুসারে এলিমেন্ট নির্বাচন করতে পারেন (যেমন সর্বনিম্ন বা সর্বাধিক মান অনুসারে)।
2. Heap Sort: Heap ব্যবহার করে সাজানো ডেটাকে সঠিকভাবে সাজানো যায়, যা একটি নন-কমপ্লেক্স ও কার্যকরী সোর্টিং অ্যালগরিদম।
3. Graph Algorithms: যেমন Dijkstra's Algorithm বা Prim's Algorithm-এ Heap ব্যবহার করা হয়।

6. Heap এর বাস্তবায়ন (Implementation)

এখানে Java দিয়ে একটি Min-Heap এবং Max-Heap এর বাস্তবায়ন দেওয়া হল:

Min-Heap বাস্তবায়ন:

import java.util.Arrays;

class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    // Constructor
    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        heap = new int[capacity];
    }

    // Insert Element into MinHeap
    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is Full");
            return;
        }
        heap[size] = value;
        size++;
        heapifyUp();
    }

    // Heapify Up
    private void heapifyUp() {
        int index = size - 1;
        while (index > 0 && heap[index] < heap[parent(index)]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    // Extract Min (Root)
    public int extractMin() {
        if (size == 0) {
            System.out.println("Heap is Empty");
            return -1;
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();
        return min;
    }

    // Heapify Down
    private void heapifyDown() {
        int index = 0;
        while (leftChild(index) < size) {
            int smallerChildIndex = leftChild(index);
            if (rightChild(index) < size && heap[rightChild(index)] < heap[smallerChildIndex]) {
                smallerChildIndex = rightChild(index);
            }
            if (heap[index] < heap[smallerChildIndex]) {
                break;
            } else {
                swap(index, smallerChildIndex);
                index = smallerChildIndex;
            }
        }
    }

    // Parent, Left Child, Right Child
    private int parent(int index) { return (index - 1) / 2; }
    private int leftChild(int index) { return 2 * index + 1; }
    private int rightChild(int index) { return 2 * index + 2; }

    // Swap Method
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // Print Heap
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size)));
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.insert(10);
        minHeap.insert(20);
        minHeap.insert(5);
        minHeap.insert(30);
        
        minHeap.printHeap();
        
        System.out.println("Extracted Min: " + minHeap.extractMin());
        minHeap.printHeap();
    }
}

Max-Heap বাস্তবায়ন:

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

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

    // Insert Element into MaxHeap
    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is Full");
            return;
        }
        heap[size] = value;
        size++;
        heapifyUp();
    }

    // Heapify Up
    private void heapifyUp() {
        int index = size - 1;
        while (index > 0 && heap[index] > heap[parent(index)]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    // Extract Max (Root)
    public int extractMax() {
        if (size == 0) {
            System.out.println("Heap is Empty");
            return -1;
        }
        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();
        return max;
    }

    // Heapify Down
    private void heapifyDown() {
        int index = 0;
        while (leftChild(index) < size) {
            int largerChildIndex = leftChild(index);
            if (rightChild(index) < size && heap[rightChild(index)] > heap[largerChildIndex]) {
                largerChildIndex = rightChild(index);
            }
            if (heap[index] > heap[largerChildIndex]) {
                break;
            } else {
                swap(index, largerChildIndex);
                index = largerChildIndex;
            }
        }
    }

    // Parent, Left Child, Right Child
    private int parent(int index) { return (index - 1) / 2; }
    private int leftChild(int index) { return 2 * index + 1; }
    private int rightChild(int index) { return 2 * index + 2; }

    // Swap Method
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // Print Heap
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size)));
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        maxHeap.insert(30);
        
        maxHeap.printHeap();
        
        System.out.println("Extracted Max: " + maxHeap.extractMax());
        maxHeap.printHeap();
    }
}

Heap একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা Min-Heap এবং Max-Heap এর মাধ্যমে ডেটা সঞ্চয়ন ও প্রক্রিয়া করার জন্য ব্যবহৃত হয়। Min-Heap এবং Max-Heap প্রতিটির নিজস্ব বৈশিষ্ট্য এবং ব্যবহার রয়েছে, যা ডাটা অনুসন্ধান, সোর্টিং এবং অন্যান্য কার্যক্রমে সহায়তা করে। Heap Sort, Priority Queue, এবং Graph Algorithms এ Heap ব্যবহার করা হয়, এবং এর কার্যকারিতা O(log n) সময়ের মধ্যে ইনসার্ট, ডিলিট এবং মিন/ম্যাক্স অপারেশন করা সম্ভব।

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 ব্যবহার করে দ্রুত এবং কার্যকরভাবে ডেটা সজ্জিত করতে সাহায্য করে।

Heap হল একটি বিশেষ ধরনের বাইনারি ট্রি ডাটা স্ট্রাকচার যা complete binary tree (পূর্ণ বাইনারি ট্রি) এর বৈশিষ্ট্য ধারণ করে। এতে একটি নির্দিষ্ট ordering property থাকে যা এটি Max-Heap বা Min-Heap হিসেবে পরিচিত করে।

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

Heap অপারেশনগুলি যেমন Insertion, Deletion, এবং Heapify অত্যন্ত গুরুত্বপূর্ণ। এগুলি Priority Queue তে ব্যবহৃত হয় এবং sorting algorithms যেমন Heap Sort এ ব্যবহৃত হয়।

এই টিউটোরিয়ালে আমরা Heap এর সাধারণ অপারেশনগুলি যেমন Insertion, Deletion, এবং Heapify সম্পর্কে আলোচনা করব এবং সেগুলি Java তে কিভাবে বাস্তবায়িত করা যায়, তা দেখাব।

1. Heap Structure Overview

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

2. Heap Operations

Heap এর তিনটি গুরুত্বপূর্ণ অপারেশন হল:

• Insertion: একটি নতুন উপাদান যুক্ত করা।
• Deletion: সর্বোচ্চ বা সর্বনিম্ন মানের উপাদান মুছে ফেলা।
• Heapify: গাছের অবস্থা বজায় রাখতে Heapify অপারেশনটি ব্যবহার করা হয়।

3. Insertion in Heap

Heap এ নতুন উপাদান ইনসার্ট করার জন্য, প্রথমে উপাদানটি গাছের শেষ স্তরে যোগ করা হয় এবং তারপর সেটিকে উপরের দিকে সঠিক স্থানে নিয়ে আসা হয় (যাকে বলা হয় heapify-up বা bubble-up) যাতে Heap Property বজায় থাকে।

3.1. Insertion Algorithm

1. নতুন উপাদানকে গাছের শেষ স্তরে যোগ করুন।
2. প্যারেন্ট নোডের সাথে নতুন উপাদানের মান তুলনা করুন:
   • যদি Max-Heap হয়, এবং নতুন উপাদান প্যারেন্ট নোডের চেয়ে বড় হয়, তবে প্যারেন্ট নোডের সাথে তাদের স্থান বদলান।
   • যদি Min-Heap হয়, এবং নতুন উপাদান প্যারেন্ট নোডের চেয়ে ছোট হয়, তবে প্যারেন্ট নোডের সাথে তাদের স্থান বদলান।
3. এই প্রক্রিয়া চলতে থাকবে যতক্ষণ না নতুন উপাদানটি সঠিক অবস্থানে পৌঁছায়।

3.2. Insertion Example in Java (Max-Heap)

import java.util.Arrays;

public class MaxHeap {
    private int[] heap;
    private int size;
    
    public MaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // Method to insert a new element
    public void insert(int value) {
        if (size == heap.length) {
            System.out.println("Heap is full");
            return;
        }
        
        // Insert the value at the last position
        heap[size] = value;
        size++;
        
        // Heapify-up
        heapifyUp(size - 1);
    }

    // Method to heapify the tree from bottom to top
    private void heapifyUp(int index) {
        while (index > 0 && heap[index] > heap[(index - 1) / 2]) {
            // Swap with parent node
            int temp = heap[index];
            heap[index] = heap[(index - 1) / 2];
            heap[(index - 1) / 2] = temp;

            index = (index - 1) / 2;
        }
    }

    // Method to print the heap
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size)));
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        maxHeap.insert(30);
        maxHeap.insert(15);

        maxHeap.printHeap();
    }
}

ব্যাখ্যা:

• insert() মেথডে উপাদানটি শেষ স্তরে যোগ করা হয়, এবং তারপর heapifyUp() মেথডের মাধ্যমে উপাদানটি সঠিক অবস্থানে নিয়ে আসা হয়।

আউটপুট:

[30, 20, 5, 10, 15]

4. Deletion in Heap

Heap থেকে উপাদান মুছে ফেলার জন্য, সাধারণত সর্বোচ্চ বা সর্বনিম্ন মান (রুট নোড) মুছে ফেলা হয়। মুছে ফেলার পর, গাছের শেষ উপাদানটি রুটে এনে heapify-down প্রক্রিয়া শুরু করা হয় যাতে Heap Property বজায় থাকে।

4.1. Deletion Algorithm

1. রুট নোডটি মুছে ফেলুন এবং গাছের শেষ উপাদানটি রুটে বসান।
2. নতুন রুট উপাদানটির সাথে প্যারেন্ট-চাইল্ড সম্পর্ক সঠিক রাখতে heapify-down অপারেশন প্রয়োগ করুন।
3. উপাদানটি সঠিক স্থানে পৌঁছানো না পর্যন্ত এই প্রক্রিয়া চালিয়ে যান।

4.2. Deletion Example in Java (Max-Heap)

public void delete() {
    if (size == 0) {
        System.out.println("Heap is empty");
        return;
    }

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

    // Heapify down from the root
    heapifyDown(0);
}

private void heapifyDown(int index) {
    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;
    int largest = index;

    // Find the largest among root, left child, and right child
    if (leftChild < size && heap[leftChild] > heap[largest]) {
        largest = leftChild;
    }
    if (rightChild < size && heap[rightChild] > heap[largest]) {
        largest = rightChild;
    }

    // Swap if needed and continue heapifying down
    if (largest != index) {
        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;

        heapifyDown(largest);
    }
}

ব্যাখ্যা:

• delete() মেথডে রুট নোডটি মুছে ফেলা হয় এবং শেষ উপাদানটি রুটে বসানো হয়। এরপর heapifyDown() মেথডের মাধ্যমে গাছের অবস্থা সঠিক রাখা হয়।

5. Heapify Operation

Heapify অপারেশন হল একটি প্রক্রিয়া যার মাধ্যমে একটি অপর্যাপ্ত গাছকে Max-Heap বা Min-Heap এ রূপান্তরিত করা হয়। সাধারণত, এটি দুটি ভাগে হয়ে থাকে:

• heapify-up: এটি ইনসার্ট অপারেশনে ব্যবহৃত হয়, যেখানে নতুন উপাদান গাছের শেষে যোগ করার পর, সেটি উপরের দিকে উঠানো হয়।
• heapify-down: এটি ডিলিশন অপারেশনে ব্যবহৃত হয়, যেখানে গাছের শীর্ষে থাকা উপাদানটি মুছে ফেলা হয় এবং গাছের শেষ উপাদানটি শীর্ষে এনে নিচে নামানো হয়।

5.1. Heapify Example (Max-Heap)

private void heapifyDown(int index) {
    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;
    int largest = index;

    // Find the largest among root, left child, and right child
    if (leftChild < size && heap[leftChild] > heap[largest]) {
        largest = leftChild;
    }
    if (rightChild < size && heap[rightChild] > heap[largest]) {
        largest = rightChild;
    }

    // Swap if needed and continue heapifying down
    if (largest != index) {
        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;

        heapifyDown(largest);
    }
}

ব্যাখ্যা:

• heapifyDown() মেথডটি গাছের নোডটি সঠিক স্থানে পৌঁছাতে সাহায্য করে যাতে Heap Property বজায় থাকে।

সারাংশ

Heap একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা গাছের আকারে থাকে এবং বিশেষত Priority Queue এবং Heap Sort এর জন্য ব্যবহৃত হয়। এর মধ্যে Insertion, Deletion, এবং Heapify অপারেশনগুলি গুরুত্বপূর্ণ।

• Insertion অপারেশনটি গাছের শেষে উপাদান যোগ করে এবং heapify-up এর মাধ্যমে সঠিক স্থানে নিয়ে আসে।
• Deletion অপারেশনটি রুট নোড মুছে ফেলে এবং heapify-down এর মাধ্যমে গাছের অবস্থান ঠিক রাখে।
• Heapify অপারেশনটি গাছকে Max-Heap বা Min-Heap এ রূপান্তরিত করতে ব্যবহৃত হয়।

এই অপারেশনগুলি ব্যবহার করে, Heap ডাটা স্ট্রাকচারটি priority scheduling, sorting algorithms, এবং graph algorithms এর মতো বিভিন্ন ক্ষেত্রে ব্যবহৃত হয়।

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 অনেক ক্ষেত্রে এটি একটি শক্তিশালী অ্যালগরিদম হিসেবে প্রমাণিত হয়েছে।