বাইনারি হিপ (Binary Heap)

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

বাইনারি হিপের বৈশিষ্ট্য

সম্পূর্ণ বাইনারি ট্রি: বাইনারি হিপ সর্বদা একটি সম্পূর্ণ বাইনারি ট্রি থাকে, যার অর্থ এটি সর্বশেষ স্তর ছাড়া সকল স্তরে পূর্ণ থাকে।

হিপ প্রোপার্টি:

• মিন হিপ: প্রতিটি পিতার নোডের মান তার সন্তানের নোডগুলির মানের তুলনায় কম অথবা সমান।
• ম্যাক্স হিপ: প্রতিটি পিতার নোডের মান তার সন্তানের নোডগুলির মানের তুলনায় বেশি অথবা সমান।

বাইনারি হিপের কার্যকারিতা

ইনসার্ট (Insert): একটি নতুন উপাদান হিপে যুক্ত করা।

• সময় জটিলতা: O(log n)

মিন/ম্যাক্স (Min/Max): হিপ থেকে সর্বনিম্ন বা সর্বাধিক উপাদান বের করা।

• সময় জটিলতা: O(1)

ডিলিট (Delete): হিপ থেকে সর্বনিম্ন বা সর্বাধিক উপাদান মুছে ফেলা এবং হিপ প্রোপার্টি বজায় রাখা।

• সময় জটিলতা: O(log n)

বিল্ডিং (Building): একটি অ্যারের ভিত্তিতে হিপ তৈরি করা।

• সময় জটিলতা: O(n)

উদাহরণ (পাইথনে মিন হিপ)

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, val):
        self.heap.append(val)
        self._bubble_up(len(self.heap) - 1)

    def _bubble_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] < self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._bubble_up(parent_index)

    def get_min(self):
        return self.heap[0] if self.heap else None

    def delete_min(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._bubble_down(0)
        return root

    def _bubble_down(self, index):
        smallest = index
        left = 2 * index + 1
        right = 2 * index + 2

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._bubble_down(smallest)

# ব্যবহার
min_heap = MinHeap()
min_heap.insert(10)
min_heap.insert(5)
min_heap.insert(3)
min_heap.insert(8)

print("Minimum element:", min_heap.get_min())  # আউটপুট: Minimum element: 3
print("Deleted minimum element:", min_heap.delete_min())  # আউটপুট: Deleted minimum element: 3
print("New minimum element:", min_heap.get_min())  # আউটপুট: New minimum element: 5

উপসংহার

বাইনারি হিপ একটি কার্যকরী ডেটা স্ট্রাকচার যা দ্রুত সর্বনিম্ন বা সর্বাধিক উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়। এটি ডেটার কার্যকরী সঞ্চয় ও পরিচালনার জন্য উপযোগী। মিন হিপ এবং ম্যাক্স হিপ উভয়ই বিভিন্ন অ্যাপ্লিকেশনে যেমন প্রায়োগিক কাজের শিডিউলিং, প্রায়োগিক এলগরিদম (যেমন হিপসোর্ট) ইত্যাদিতে গুরুত্বপূর্ণ ভূমিকা পালন করে।

মাক্স-হিপ এবং মিন-হিপের ধারণা

হিপ (Heap) হলো একটি বিশেষ ধরনের বাইনারি ট্রি, যা একটি সম্পূর্ণ বাইনারি ট্রি আকারে সাজানো থাকে। হিপের দুটি প্রধান প্রকারভেদ রয়েছে: মাক্স-হিপ (Max-Heap) এবং মিন-হিপ (Min-Heap)। এই ডেটা স্ট্রাকচারটি সাধারণত প্রায়োরিটি কিউ, ডেটা প্রসেসিং এবং দ্রুততম উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়।

১. মাক্স-হিপ (Max-Heap)

মাক্স-হিপ এমন একটি হিপ যেখানে প্রতিটি প্যারেন্ট নোড তার সমস্ত চাইল্ড নোডগুলির চেয়ে বড় বা সমান মান ধারণ করে। মাক্স-হিপের মূল নোড বা রুট সর্বোচ্চ মান ধারণ করে।

বৈশিষ্ট্য:

• প্রতিটি প্যারেন্ট নোডের মান তার চাইল্ড নোডগুলোর মানের চেয়ে বড় বা সমান হবে।
• রুট নোডে সর্বাধিক মান থাকে।

উদাহরণ:

একটি মাক্স-হিপের উদাহরণ নিচে দেওয়া হলো:

       50
      /    \
    30     40
   /   \   /   \
 10   15 20   35

এখানে, 50 হলো রুট এবং এটি সর্বাধিক মান, এবং প্রতিটি প্যারেন্ট নোড তার চাইল্ড নোডের চেয়ে বড়।

মাক্স-হিপের ব্যবহার:

• প্রায়োরিটি কিউ: মাক্স-হিপ ব্যবহার করে সর্বোচ্চ প্রায়োরিটি আইটেম দ্রুত খুঁজে বের করা যায়।
• সাজানো ডেটা খুঁজে বের করা: হিপ সর্টিংয়ের জন্য মাক্স-হিপ ব্যবহার করা হয়।

২. মিন-হিপ (Min-Heap)

মিন-হিপ এমন একটি হিপ যেখানে প্রতিটি প্যারেন্ট নোড তার সমস্ত চাইল্ড নোডগুলির চেয়ে ছোট বা সমান মান ধারণ করে। মিন-হিপের মূল নোড বা রুট সর্বনিম্ন মান ধারণ করে।

বৈশিষ্ট্য:

• প্রতিটি প্যারেন্ট নোডের মান তার চাইল্ড নোডগুলোর মানের চেয়ে ছোট বা সমান হবে।
• রুট নোডে সর্বনিম্ন মান থাকে।

উদাহরণ:

একটি মিন-হিপের উদাহরণ নিচে দেওয়া হলো:

       10
      /    \
    15     20
   /   \   /   \
 30   40 35   50

এখানে, 10 হলো রুট এবং এটি সর্বনিম্ন মান, এবং প্রতিটি প্যারেন্ট নোড তার চাইল্ড নোডের চেয়ে ছোট।

মিন-হিপের ব্যবহার:

• প্রায়োরিটি কিউ: মিন-হিপ ব্যবহার করে সর্বনিম্ন প্রায়োরিটি আইটেম দ্রুত খুঁজে বের করা যায়।
• ডেটা প্রসেসিং: ডেটার মধ্যে সবচেয়ে ছোট মান দ্রুত খুঁজে বের করতে মিন-হিপ ব্যবহার করা হয়।

মাক্স-হিপ এবং মিন-হিপের তুলনামূলক চার্ট

উদাহরণ: মাক্স-হিপ এবং মিন-হিপ (Python কোড)

Python-এ মিন-হিপ তৈরি করতে heapq মডিউল ব্যবহার করা যায়। তবে, মাক্স-হিপের জন্য heapq কে উল্টো মান ব্যবহার করে মিন-হিপের মতো করে কাজ করানো যায়।

import heapq

# মিন-হিপ উদাহরণ
min_heap = []
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 15)
heapq.heappush(min_heap, 5)
print("Min-Heap:", min_heap)  # আউটপুট: Min-Heap: [5, 15, 10]

# মাক্স-হিপ উদাহরণ
max_heap = []
heapq.heappush(max_heap, -10)  # মানটি নেগেটিভ করে ইনসার্ট করা হয়
heapq.heappush(max_heap, -15)
heapq.heappush(max_heap, -5)
print("Max-Heap:", [-x for x in max_heap])  # আউটপুট: Max-Heap: [15, 10, 5]

উপসংহার

মাক্স-হিপ এবং মিন-হিপ ডেটা স্ট্রাকচারগুলো বিশেষত প্রায়োরিটি কিউ এবং হিপ সর্টে ব্যবহৃত হয়। মাক্স-হিপ সর্বোচ্চ মান খুঁজে বের করতে এবং মিন-হিপ সর্বনিম্ন মান খুঁজে বের করতে কার্যকর।

হিপ (Heap) একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা পূর্ণ বাইনারি ট্রি ভিত্তিক। এটি প্রধানত দুটি ধরনের হয়: ম্যাক্স হিপ (Max Heap) এবং মিন হিপ (Min Heap)। ম্যাক্স হিপে, প্রতিটি পিতার মান তার সন্তানের মানের চেয়ে বড় হয়, এবং মিন হিপে, প্রতিটি পিতার মান তার সন্তানের মানের চেয়ে ছোট হয়। হিপটি মূলত একটি সিকোয়েন্স বা প্যারেন্ট-চাইল্ড সম্পর্কযুক্ত ডেটার সংরক্ষণ ও পরিচালনার জন্য ব্যবহৃত হয়।

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

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

বিবরণ: একটি নতুন উপাদান হিপে যুক্ত করার প্রক্রিয়া।

কাজের পদ্ধতি:

1. নতুন উপাদানটি হিপের শেষের দিকে যোগ করা হয় (এটি একটি পূর্ণ বাইনারি ট্রির নিয়ম অনুসরণ করে)।
2. নতুন উপাদানটির জন্য পিতার সাথে তুলনা করা হয় এবং প্রয়োজনে এটি উপরে উঠানো হয় (বাবা উপরে যেতে থাকে)।
3. এই প্রক্রিয়াটি চলতে থাকে যতক্ষণ না হিপের গঠন বজায় থাকে।

উদাহরণ (ম্যাক্স হিপ):

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # বিনিময়
        heapify(arr, n, largest)

def insert(arr, key):
    arr.append(key)  # নতুন উপাদান যুক্ত করা
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)  # হিপ গঠন বজায় রাখা

# ব্যবহার
heap = [10, 20, 30]
insert(heap, 25)
print(heap)  # আউটপুট: [30, 20, 10, 25]

২. ডিলিট (Delete)

বিবরণ: হিপ থেকে সর্বাধিক (ম্যাক্স হিপ) বা সর্বনিম্ন (মিন হিপ) উপাদান মুছে ফেলার প্রক্রিয়া।

কাজের পদ্ধতি:

1. রুট উপাদান (ম্যাক্স বা মিন) মুছে ফেলুন।
2. হিপের শেষ উপাদানকে রুটের স্থানে রাখুন।
3. নতুন রুটের জন্য হিপ গঠন বজায় রাখুন।

উদাহরণ (ম্যাক্স হিপ):

def delete_root(arr):
    n = len(arr)
    if n == 0:
        return None
    if n == 1:
        return arr.pop()  # একমাত্র উপাদান মুছে ফেলুন

    root = arr[0]  # রুট সংরক্ষণ করুন
    arr[0] = arr[-1]  # শেষ উপাদানকে রুটে রাখুন
    arr.pop()  # শেষ উপাদান মুছে ফেলুন
    heapify(arr, n - 1, 0)  # হিপ গঠন বজায় রাখা

    return root  # রুটের মান রিটার্ন করুন

# ব্যবহার
heap = [30, 20, 10]
print(delete_root(heap))  # আউটপুট: 30
print(heap)  # আউটপুট: [20, 10]

৩. এক্সট্র্যাক্ট-ম্যাক্স/মিন (Extract-Max/Min)

বিবরণ: সর্বাধিক (ম্যাক্স হিপের জন্য) বা সর্বনিম্ন (মিন হিপের জন্য) উপাদানটি বের করার প্রক্রিয়া।

কাজের পদ্ধতি:

1. রুট উপাদানটি (সর্বাধিক বা সর্বনিম্ন) ফিরিয়ে দিন।
2. ডিলিট অপারেশনটি ব্যবহার করে রুট উপাদানটিকে হিপ থেকে সরান।

উদাহরণ (ম্যাক্স হিপ):

def extract_max(arr):
    if len(arr) == 0:
        return None
    return delete_root(arr)  # সর্বাধিক উপাদান বের করুন

# ব্যবহার
heap = [30, 20, 10]
print(extract_max(heap))  # আউটপুট: 30
print(heap)  # আউটপুট: [20, 10]

উপসংহার

হিপ অপারেশনগুলি যেমন ইনসার্ট, ডিলিট, এবং এক্সট্র্যাক্ট-ম্যাক্স/মিন গুরুত্বপূর্ণ ডেটা পরিচালনার কৌশল। এগুলি বিভিন্ন প্রোগ্রামিং সমস্যায়, যেমন সর্বাধিক বা সর্বনিম্ন মান বের করতে, অথবা অর্ডারড ডেটা গঠন করতে ব্যবহৃত হয়। হিপের কার্যকারিতা ও সময় জটিলতা O(log n) হওয়ার কারণে, এটি দ্রুত কাজ করার জন্য উপযুক্ত।

হিপ (Heap) এর অ্যাপ্লিকেশন

হিপ হল একটি বিশেষ ধরনের বাইনারি ট্রি যা পূর্ণ বা পারেন্ট নোডের মান সবসময় তার চাইল্ড নোডের মানের চেয়ে বড় (ম্যাক্স হিপ) বা ছোট (মিন হিপ) থাকে। এটি বিভিন্ন অ্যাপ্লিকেশনে ব্যবহৃত হয়, যেমন প্রাইমারি এলিমেন্ট সার্চ এবং হাফম্যান কোডিং।

১. প্রাইমারি এলিমেন্ট সার্চ (Priority Queue)

বর্ণনা

প্রাইমারি এলিমেন্ট সার্চ হল একটি ডেটা স্ট্রাকচার যা এলিমেন্টগুলিকে তাদের প্রাধান্য অনুযায়ী সজ্জিত করে। হিপ ব্যবহার করে প্রাইমারি কিউ তৈরি করা হয়, যেখানে এলিমেন্টগুলি তাদের প্রাধান্যের ভিত্তিতে ইনসার্ট এবং এক্সট্র্যাক্ট করা হয়।

উদাহরণ

1. মিন হিপ: সর্বনিম্ন প্রাধান্যের এলিমেন্ট সর্বদা হিপের শীর্ষে থাকে।
2. ম্যাক্স হিপ: সর্বাধিক প্রাধান্যের এলিমেন্ট সর্বদা হিপের শীর্ষে থাকে।

ব্যবহার

• ডাটাবেসের অর্ডারিং: প্রাইমারি কিউ ব্যবহার করে ডেটাবেসে রেকর্ডগুলিকে প্রাধান্যের ভিত্তিতে সনাক্ত করা।
• অ্যাপ্লিকেশন: কাজের তালিকা তৈরি করা যেখানে উচ্চ প্রাধান্যের কাজগুলি প্রথমে সম্পন্ন করতে হয়।

উদাহরণ কোড (Python):

import heapq

# মিন হিপ ব্যবহার করে প্রাইমারি কিউ তৈরি করা
priority_queue = []

# এলিমেন্ট যুক্ত করা
heapq.heappush(priority_queue, (2, 'task2'))
heapq.heappush(priority_queue, (1, 'task1'))
heapq.heappush(priority_queue, (3, 'task3'))

# এলিমেন্ট বের করা
while priority_queue:
    print(heapq.heappop(priority_queue)[1])  # Output: task1, task2, task3

২. হাফম্যান কোডিং (Huffman Coding)

বর্ণনা

হাফম্যান কোডিং হল একটি প্রকারের ডেটা সংকোচনের অ্যালগরিদম যা ট্রি ব্যবহার করে বিভিন্ন অক্ষরের জন্য কোড তৈরি করে। হাফম্যান অ্যালগরিদমের সময় হিপ ব্যবহার করা হয় অক্ষরের প্রাধান্য অনুযায়ী।

পদ্ধতি

1. অক্ষরের ফ্রিকোয়েন্সি অনুযায়ী একটি মিন হিপ তৈরি করুন।
2. হিপের দুটি সর্বনিম্ন ফ্রিকোয়েন্সি নোড নিয়ে একটি নতুন নোড তৈরি করুন এবং সেটিকে হিপে পুনরায় যুক্ত করুন।
3. এই প্রক্রিয়া চলতে থাকবে যতক্ষণ না হিপে একটি মাত্র নোড থাকে, যা হাফম্যান ট্রি হিসেবে কাজ করবে।

ব্যবহার

• ডেটা সংকোচন: হাফম্যান কোডিং ব্যবহার করে টেক্সট ফাইল এবং অন্যান্য ডেটাকে সংকুচিত করা।

উদাহরণ কোড (Python):

import heapq
from collections import defaultdict

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def huffman_coding(frequencies):
    heap = []
    
    # নোড তৈরি করা
    for char, freq in frequencies.items():
        heapq.heappush(heap, Node(char, freq))

    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    return heap[0]  # হাফম্যান ট্রি

# উদাহরণ
frequencies = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}
huffman_tree = huffman_coding(frequencies)

উপসংহার

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