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

হিপ (Heap) একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা সম্পূর্ণ বাইনারি ট্রি (Complete Binary Tree) গঠন করে এবং এটি একটি নির্দিষ্ট অর্ডারে উপাদানগুলিকে সঞ্চয় করে। হিপের দুটি প্রধান ধরনের হিপ রয়েছে: ম্যাক্স হিপ (Max Heap) এবং মিন হিপ (Min Heap)।

• ম্যাক্স হিপ: প্রতিটি নোডের মান তার সন্তানদের মানের থেকে বড় বা সমান হয়।
• মিন হিপ: প্রতিটি নোডের মান তার সন্তানদের মানের থেকে ছোট বা সমান হয়।

হিপ সাধারণত হিপ_SORT অ্যালগরিদম, প্রাধিকারের কিউ (Priority Queue), এবং ডেটা সঞ্চয়ের জন্য ব্যবহৃত হয়।

১. হিপের গঠন

হিপ সাধারণত একটি অ্যারের মাধ্যমে বাস্তবায়িত হয়। এটির গঠন নিম্নরূপ:

• পিতৃ নোডের ইনডেক্স i থাকলে,
  • বাম সন্তানের ইনডেক্স: 2*i + 1
  • ডান সন্তানের ইনডেক্স: 2*i + 2

২. হিপের অপারেশন

২.১ ইনসার্ট (Insert)

নতুন একটি উপাদান হিপে যোগ করার জন্য ইনসার্ট অপারেশন ব্যবহার করা হয়। উপাদানটি হিপের শেষের দিকে যুক্ত করা হয় এবং তারপর হিপের বৈশিষ্ট্য বজায় রাখতে উপরের দিকে উঠানো হয়।

২.২ এক্সট্র্যাক্ট ম্যাক্স (Extract Max)

ম্যাক্স হিপ থেকে সর্বাধিক মান অপসারণ করার জন্য এক্সট্র্যাক্ট ম্যাক্স অপারেশন ব্যবহার করা হয়। সর্বাধিক মানটি শিকড়ে থাকে, এবং এটি অপসারণের পর হিপের বৈশিষ্ট্য বজায় রাখতে পুনরুদ্ধার করা হয়।

২.৩ হিপিফাই (Heapify)

হিপিফাই অপারেশন ব্যবহার করে একটি নোডের জন্য হিপের বৈশিষ্ট্য বজায় রাখা হয়। যদি কোনও নোড তার সন্তানদের থেকে বড় না হয়, তবে এটি তাদের সাথে বিনিময় করে এবং এই প্রক্রিয়াটি চলতে থাকে।

হিপ (Heap) এর ধারণা এবং প্রয়োগ

হিপ (Heap) একটি বিশেষ ধরনের বাইনারি ট্রি ডেটা স্ট্রাকচার, যা সম্পূর্ণ বাইনারি ট্রি হিসেবে গঠিত এবং এতে প্রতিটি নোডের মান তার সন্তানের মানের তুলনায় বড় বা ছোট হয়। হিপকে সাধারণত Max-Heap (যেখানে পিতার মান সন্তানের মান থেকে বড়) অথবা Min-Heap (যেখানে পিতার মান সন্তানের মান থেকে ছোট) হিসেবে শ্রেণীবদ্ধ করা হয়।

হিপের ধারণা

হিপ একটি পূর্ণ বাইনারি ট্রি (Complete Binary Tree) যা দুটি গুরুত্বপূর্ণ শর্ত মেনে চলে:

1. প্রতিটি স্তরে পিতার মান সন্তানের মানের তুলনায় বড় বা ছোট হয়:
   • Max-Heap: প্রতিটি পিতার মান তার সন্তানদের মান থেকে বড়।
   • Min-Heap: প্রতিটি পিতার মান তার সন্তানদের মান থেকে ছোট।
2. পূর্ণ বাইনারি ট্রি: এটি একটি বাইনারি ট্রি, যেখানে প্রতি স্তরে প্রতিটি নোডের দুটি সন্তান থাকতে পারে এবং সর্বশেষ স্তরটি সম্পূর্ণভাবে পূর্ণ হয়, ব্যতীত সর্বশেষ স্তরের নোডগুলির ক্ষেত্রে, যা বাম থেকে ডানদিকে পূর্ণ হয়।

হিপের গঠন

• Max-Heap: এখানে প্রতিটি পিতার মান তার সন্তানের মানের থেকে বড় থাকে এবং রুট নোডটি সর্বোচ্চ মান ধারণ করে।
• Min-Heap: এখানে প্রতিটি পিতার মান তার সন্তানের মানের থেকে ছোট থাকে এবং রুট নোডটি সর্বনিম্ন মান ধারণ করে।

হিপের প্রধান অপারেশনসমূহ

1. ইনসার্ট (Insert): একটি নতুন উপাদান হিপে যুক্ত করা হয়। ইনসার্ট করার পর উপযুক্ত স্থানে উপাদানটি বসাতে আপ-হিপ অপারেশন করা হয়।
2. এক্সট্রাকশন (Extraction): সর্বোচ্চ বা সর্বনিম্ন মানের উপাদান রুট থেকে মুছে ফেলা হয় এবং হিপ গঠন ঠিক রাখতে ডাউন-হিপ অপারেশন করা হয়।
3. হিপিফাই (Heapify): একটি উপাদান সরানো বা পরিবর্তন করার পরে হিপের কাঠামো ঠিক রাখতে হিপিফাই করা হয়।

হিপের প্রয়োগ

1. প্রাইরিটি কিউ (Priority Queue):

   • হিপকে প্রাইরিটি কিউ তৈরি করার জন্য ব্যবহৃত হয়, যেখানে প্রতিটি উপাদান একটি প্রাইরিটি ধারণ করে। সর্বোচ্চ (Max-Heap) বা সর্বনিম্ন (Min-Heap) প্রাইরিটি উপাদানটি সহজে বের করা যায়। উদাহরণস্বরূপ, একটি প্রিন্টার কিউ বা একটি নেটওয়ার্ক ডাটা কিউ।

   উদাহরণ: যদি একটি প্রাইরিটি কিউতে বিভিন্ন কাজ থাকে, তাহলে হিপের সাহায্যে সর্বোচ্চ প্রাইরিটি কাজ প্রথমে সম্পন্ন হবে।

2. হিপ সোর্ট (Heap Sort):

   • হিপ সোর্ট একটি কমপ্লেক্স সোর্টিং অ্যালগরিদম, যা O(n log n) সময়ে কাজ করে। এটি Max-Heap বা Min-Heap ব্যবহার করে একটি অ্যারে সজ্জিত করে।

   প্রক্রিয়া:

   • প্রথমে একটি হিপ তৈরি করা হয় (Max-Heap বা Min-Heap)।
   • তারপর হিপের রুট থেকে সর্বোচ্চ বা সর্বনিম্ন মানে উপাদানটি বের করে হিপ থেকে সরিয়ে ফেলা হয় এবং বাকী অংশটির হিপিফাই করা হয়।
3. ডাইকস্ট্রা অ্যালগরিদম (Dijkstra's Algorithm):
   • হিপের সাহায্যে ডাইকস্ট্রার অ্যালগরিদমে সেরা পথ খোঁজা হয়, যেখানে গ্রাফের শীর্ষ থেকে গন্তব্যের দিকে সর্বনিম্ন মানের পথটি নির্বাচন করা হয়। এখানে Min-Heap ব্যবহার করা হয়।
4. গ্রীড সিকোয়েন্সিং (Grid Sequencing):
   • কোনো সিস্টেমে বিভিন্ন ভিন্ন ডেটা প্রক্রিয়া করার জন্য হিপ ব্যবহৃত হতে পারে যেখানে একটি নির্দিষ্ট ক্রমে ডেটা প্রক্রিয়া করার প্রয়োজন হয়।

হিপের ব্যবহার

1. প্রাইরিটি কিউ:

   • এটির মাধ্যমে আপনি এমন কিউ তৈরি করতে পারেন যেখানে যেকোনো সময় সর্বোচ্চ বা সর্বনিম্ন প্রাইরিটি আইটেমকে সরিয়ে নেওয়া হয়।

   ব্যবহার:

   • এয়ারলাইন টিকেটের কিউ সিস্টেম, থ্রেড স্কেজুলিং, টাস্ক সিডিউলিং।
2. হিপ সোর্ট:
   • এটি একটি অ্যালগরিদম যা হিপ ডেটা স্ট্রাকচার ব্যবহার করে অর্ডারিং প্রক্রিয়া সম্পন্ন করে।
3. ডাইকস্ট্রার অ্যালগরিদম:
   • মিন হিপ গ্রাফ অ্যালগরিদমের জন্য ব্যবহার করা হয়, যেখানে একটি সেরা রুট খোঁজার জন্য হিপ ডেটা স্ট্রাকচার ব্যবহৃত হয়।

সারসংক্ষেপ

হিপ একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা Max-Heap এবং Min-Heap গঠন অনুসরণ করে এবং এটি বিভিন্ন সমস্যার সমাধানে ব্যবহৃত হয়। হিপ সঠিক সময়ে দ্রুত প্রাইরিটি কিউ অপারেশন, সোর্টিং এবং গ্রাফ অ্যালগরিদম সমাধানে সহায়তা করে। এটি সি প্রোগ্রামিং ভাষায় ব্যবহার করা হলে কার্যকরী হয় এবং বিভিন্ন অ্যালগরিদমে অবলম্বিত হয় যেমন হিপ সোর্ট, ডাইকস্ট্রার অ্যালগরিদম, এবং প্রাইরিটি কিউ প্রক্রিয়া।

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

Max-Heap এবং Min-Heap দুটি আলাদা হিপ গঠন। Max-Heap-এ প্রতিটি নোডের মান তার সন্তানের মানের থেকে বড় হয়, আর Min-Heap-এ প্রতিটি নোডের মান তার সন্তানের মানের থেকে ছোট হয়। এখন আমরা Max-Heap এবং Min-Heap এর সি প্রোগ্রামিং ভাষায় ইমপ্লিমেন্টেশন দেখবো।

Max-Heap এর ইমপ্লিমেন্টেশন

Max-Heap ইমপ্লিমেন্ট করার জন্য ইনসার্ট (insert), এক্সট্র্যাক্ট (extract) এবং হিপিফাই (heapify) ফাংশন প্রয়োজন হয়।

Max-Heap এর সি কোড:

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

// Insert an element into the heap
void insert(int value) {
    if (size == MAX) {
        printf("Heap 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 root (max) element
int extractMax() {
    if (size == 0) {
        printf("Heap Underflow\n");
        return -1;
    }

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

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

int main() {
    insert(10);
    insert(20);
    insert(5);
    insert(30);
    insert(40);

    printf("Max-Heap: ");
    printHeap();

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

    printf("Max-Heap after extraction: ");
    printHeap();

    return 0;
}

Min-Heap এর ইমপ্লিমেন্টেশন

Min-Heap-এ প্রতিটি নোডের মান তার সন্তানের মানের থেকে ছোট হয়। এটি Max-Heap এর বিপরীত।

Min-Heap এর সি কোড:

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

    // Left child is smaller
    if (left < size && heap[left] < heap[smallest]) {
        smallest = left;
    }

    // Right child is smaller
    if (right < size && heap[right] < heap[smallest]) {
        smallest = right;
    }

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

// Insert an element into the heap
void insert(int value) {
    if (size == MAX) {
        printf("Heap 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 root (min) element
int extractMin() {
    if (size == 0) {
        printf("Heap Underflow\n");
        return -1;
    }

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

    return min;
}

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

int main() {
    insert(10);
    insert(20);
    insert(5);
    insert(30);
    insert(40);

    printf("Min-Heap: ");
    printHeap();

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

    printf("Min-Heap after extraction: ");
    printHeap();

    return 0;
}

Max-Heap এবং Min-Heap এর মধ্যে পার্থক্য

• Max-Heap:
  • রুট নোড সর্বোচ্চ মান ধারণ করে।
  • প্রতিটি পিতার মান তার সন্তানের মানের থেকে বড় থাকে।
• Min-Heap:
  • রুট নোড সর্বনিম্ন মান ধারণ করে।
  • প্রতিটি পিতার মান তার সন্তানের মানের থেকে ছোট থাকে।

সারসংক্ষেপ

• Max-Heap এবং Min-Heap দুটি আলাদা হিপ গঠন যা সি প্রোগ্রামিং ভাষায় কার্যকরীভাবে ব্যবহার করা যায়।
• Max-Heap সর্বোচ্চ মানের উপাদান বের করার জন্য ব্যবহৃত হয়, যেখানে Min-Heap সর্বনিম্ন মানের উপাদান বের করার জন্য ব্যবহৃত হয়।
• এই দুটি হিপ গঠন ইনসার্ট, এক্সট্র্যাক্ট, এবং হিপিফাই অপারেশন ব্যবহার করে পরিচালিত হয়।

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 বিভিন্ন প্রোগ্রামিং অ্যাপ্লিকেশন যেমন গ্রাফ অ্যালগরিদম, সিস্টেম সিডিউলিং, এবং অন্যান্য কাজের জন্য ব্যবহৃত হয়।

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) এবং অন্যান্য টাস্ক সিডিউলিং ক্ষেত্রে।