Computer Programming Priority Queue এর জন্য Heap ব্যবহার গাইড ও নোট

Priority Queue এর জন্য Heap ব্যবহার

Priority Queue একটি বিশেষ ধরনের কিউ (Queue) ডেটা স্ট্রাকচার, যেখানে প্রতিটি উপাদান একটি প্রাইরিটি (priority) ধারণ করে। প্রাইরিটি কিউতে সাধারণ কিউর তুলনায়, উপাদানগুলোকে FIFO (First-In-First-Out) নিয়মে সরানোর বদলে তাদের প্রাইরিটির ওপর ভিত্তি করে বের করা হয়। এর মানে, সর্বোচ্চ প্রাইরিটি (Max-Heap) বা সর্বনিম্ন প্রাইরিটি (Min-Heap) উপাদানটি আগে বের হয়।

Heap একটি বাইনারি ট্রি ডেটা স্ট্রাকচার যা প্রাইরিটি কিউ তৈরি করতে ব্যবহার করা হয়। হিপের মাধ্যমে কিউ থেকে সর্বোচ্চ বা সর্বনিম্ন প্রাইরিটি উপাদানটি দ্রুত বের করা সম্ভব হয়।

Priority Queue এর জন্য Heap ব্যবহার:

1. Max-Heap: যদি কিউটি সর্বোচ্চ প্রাইরিটি উপাদানকে আগে বের করে, তবে আমরা Max-Heap ব্যবহার করি। এতে রুট নোড সর্বোচ্চ প্রাইরিটি ধারণ করে।
2. Min-Heap: যদি কিউটি সর্বনিম্ন প্রাইরিটি উপাদানকে আগে বের করে, তবে আমরা Min-Heap ব্যবহার করি। এতে রুট নোড সর্বনিম্ন প্রাইরিটি ধারণ করে।

Priority Queue এর জন্য Max-Heap এবং Min-Heap এর ইমপ্লিমেন্টেশন

এখানে আমরা একটি সাধারণ প্রাইরিটি কিউ তৈরি করব যা Max-Heap ব্যবহার করে। আপনি চাইলে Min-Heap ব্যবহার করে সর্বনিম্ন প্রাইরিটি উপাদানও বের করতে পারেন।

Max-Heap ভিত্তিক Priority Queue এর সি কোড:

#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;

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

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

    if (largest != i) {
        swap(&heap[i], &heap[largest]);
        heapify(largest);
    }
}

// Insert an element into the priority queue (Max-Heap)
void insert(int value) {
    if (size == MAX) {
        printf("Priority Queue Overflow\n");
        return;
    }

    heap[size++] = value;
    int i = size - 1;

    // Move the inserted value to its correct position
    while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Extract the highest priority element (root of Max-Heap)
int extractMax() {
    if (size == 0) {
        printf("Priority Queue Underflow\n");
        return -1;
    }

    int max = heap[0];
    heap[0] = heap[--size];
    heapify(0);

    return max;
}

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

int main() {
    // Insert elements with priority
    insert(10);
    insert(30);
    insert(20);
    insert(50);
    insert(40);

    printf("Priority Queue (Max-Heap): ");
    printPriorityQueue();

    printf("Extract Max (Highest priority): %d\n", extractMax());

    printf("Priority Queue after extraction: ");
    printPriorityQueue();

    return 0;
}

ব্যাখ্যা:

1. Insert Operation: নতুন উপাদানটি কিউতে যোগ করা হয় এবং heapify প্রক্রিয়া মাধ্যমে তা সঠিক স্থানে বসানো হয় যাতে সর্বোচ্চ প্রাইরিটি উপাদানটি কিউয়ের রুটে থাকে।
2. ExtractMax Operation: সর্বোচ্চ প্রাইরিটি (রুট) উপাদানটি বের করা হয় এবং কিউয়ের শেষ উপাদানকে রুটে নিয়ে আসা হয়। তারপর heapify অপারেশন চালিয়ে হিপের কাঠামো পুনরুদ্ধার করা হয়।
3. Heapify: হিপের কাঠামো ঠিক রাখতে একটি উপাদানকে তার সঠিক অবস্থানে নিয়ে যাওয়ার প্রক্রিয়া। এটি O(log n) সময়ে কাজ করে।
4. Time Complexity:
   • insert: O(log n)
   • extractMax: O(log n)
   • printPriorityQueue: O(n)

Min-Heap ভিত্তিক Priority Queue

যদি আপনি সর্বনিম্ন প্রাইরিটি উপাদানটি বের করতে চান, তবে Min-Heap ব্যবহার করতে হবে, যেখানে রুট নোড সর্বনিম্ন প্রাইরিটি ধারণ করে। নিচে Min-Heap ভিত্তিক Priority Queue এর সি কোড দেওয়া হলো:

Min-Heap ভিত্তিক Priority Queue এর সি কোড:

#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 Min-Heap property
void heapify(int i) {
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < size && heap[left] < heap[smallest]) {
        smallest = left;
    }

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

    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        heapify(smallest);
    }
}

// Insert an element into the priority queue (Min-Heap)
void insert(int value) {
    if (size == MAX) {
        printf("Priority Queue Overflow\n");
        return;
    }

    heap[size++] = value;
    int i = size - 1;

    // Move the inserted value to its correct position
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Extract the lowest priority element (root of Min-Heap)
int extractMin() {
    if (size == 0) {
        printf("Priority Queue Underflow\n");
        return -1;
    }

    int min = heap[0];
    heap[0] = heap[--size];
    heapify(0);

    return min;
}

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

int main() {
    // Insert elements with priority
    insert(10);
    insert(30);
    insert(20);
    insert(50);
    insert(40);

    printf("Priority Queue (Min-Heap): ");
    printPriorityQueue();

    printf("Extract Min (Lowest priority): %d\n", extractMin());

    printf("Priority Queue after extraction: ");
    printPriorityQueue();

    return 0;
}

Min-Heap ভিত্তিক Priority Queue এর ব্যাখ্যা:

• Insert Operation: নতুন উপাদানটি কিউতে যোগ করার সময় heapify অপারেশন ব্যবহার করে উপাদানটিকে সঠিক অবস্থানে বসানো হয়।
• ExtractMin Operation: সর্বনিম্ন প্রাইরিটি (রুট) উপাদানটি বের করা হয় এবং কিউয়ের শেষ উপাদানটিকে রুটে নিয়ে আসা হয়। তারপর heapify অপারেশন চালিয়ে হিপের কাঠামো ঠিক করা হয়।

সারসংক্ষেপ

Heap ডেটা স্ট্রাকচার ব্যবহার করে Priority Queue তৈরি করা হয় যাতে প্রাইরিটির ওপর ভিত্তি করে উপাদানগুলো বের করা যায়। Max-Heap ব্যবহার করে সর্বোচ্চ প্রাইরিটি উপাদান এবং Min-Heap ব্যবহার করে সর্বনিম্ন প্রাইরিটি উপাদান বের করা সম্ভব। Heapsort-এর মতো Priority Queue প্রোগ্রামিংয়ে অনেক কার্যকরী, বিশেষ করে গ্রাফ অ্যালগরিদম (যেমন Dijkstra’s Algorithm) এবং অন্যান্য টাস্ক সিডিউলিং ক্ষেত্রে।