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 এর অপারেশন:
- Insert: নতুন এলিমেন্ট যোগ করা।
- Extract-Min: Root (সর্বনিম্ন) এলিমেন্ট মুছে ফেলা।
- 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 এর অপারেশন:
- Insert: নতুন এলিমেন্ট যোগ করা।
- Extract-Max: Root (সর্বাধিক) এলিমেন্ট মুছে ফেলা।
- Peek: Root নোডের মান দেখা।
4. Heap এর কার্যকারিতা (Time Complexity)
Heap ডাটা স্ট্রাকচারে কিছু সাধারণ অপারেশন এবং তাদের কার্যকারিতা:
- Insert (Enqueue): O(log n)
- Extract (Dequeue): O(log n)
- Peek: O(1)
- Build Heap: O(n)
Heap ডাটা স্ট্রাকচারটি O(log n) সময়ে ইনসার্ট, ডিলিট, এবং রিইন্টারনালাইজ অপারেশন করতে সক্ষম, যা অন্যান্য স্ট্রাকচারের তুলনায় অধিক কার্যকরী।
5. Heap এর ব্যবহার
Heap বিভিন্ন ধরনের সমস্যা সমাধানে ব্যবহৃত হয়, যেমন:
- Priority Queue: Heap এর মাধ্যমে আপনি প্রাধান্য অনুসারে এলিমেন্ট নির্বাচন করতে পারেন (যেমন সর্বনিম্ন বা সর্বাধিক মান অনুসারে)।
- Heap Sort: Heap ব্যবহার করে সাজানো ডেটাকে সঠিকভাবে সাজানো যায়, যা একটি নন-কমপ্লেক্স ও কার্যকরী সোর্টিং অ্যালগরিদম।
- 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) সময়ের মধ্যে ইনসার্ট, ডিলিট এবং মিন/ম্যাক্স অপারেশন করা সম্ভব।
Read more
