28. Priority Queue
Priority Queue হলো একটি বিশেষ ধরণের কিউ (Queue) যেখানে প্রতিটি এলিমেন্টের সাথে একটি Priority বা গুরুত্ব যুক্ত থাকে। এখানে এলিমেন্টগুলো FIFO (First In First Out) এর পরিবর্তে তাদের গুরুত্ব অনুযায়ী প্রসেস করা হয়।
1. Priority Queue কি?
সাধারণ কিউ-তে যে আগে আসে সে আগে সার্ভিস পায়। কিন্তু প্রায়োরিটি কিউ-তে যার গুরুত্ব (Priority) সবচেয়ে বেশি, সে সবার আগে সার্ভিস পায়। যদি দুইজনের গুরুত্ব সমান হয়, তবে তারা কিউ-তে আসার ক্রম অনুযায়ী সার্ভিস পাবে।
2. Heap-এর ধারণা (Concept of Heap)
প্রায়োরিটি কিউ ইমপ্লিমেন্ট করার সবচেয়ে জনপ্রিয় পদ্ধতি হলো Heap। হিপ মূলত দুই ধরণের হয়:
Max Heap
এখানে প্যারেন্ট নোডের ভ্যালু সবসময় তার চাইল্ড নোডগুলোর চেয়ে বড় বা সমান হয়। ফলে রুটে (Root) সবসময় সর্বোচ্চ ভ্যালু থাকে।
Min Heap
এখানে প্যারেন্ট নোডের ভ্যালু সবসময় তার চাইল্ড নোডগুলোর চেয়ে ছোট বা সমান হয়। ফলে রুটে (Root) সবসময় সর্বনিম্ন ভ্যালু থাকে।
3. মূল অপারেশনসমূহ (Operations)
- Insert: নতুন একটি এলিমেন্টকে তার গুরুত্ব অনুযায়ী কিউ-তে যোগ করা।
- Extract Max/Min: কিউ থেকে সর্বোচ্চ বা সর্বনিম্ন গুরুত্বের এলিমেন্টটি সরিয়ে ফেলা।
- Peek: কিউ-র সবথেকে গুরুত্বপূর্ণ এলিমেন্টটি দেখা (না সরিয়ে)।
- Decrease Key: একটি এলিমেন্টের গুরুত্ব কমিয়ে দেওয়া বা আপডেট করা।
4. ইমপ্লিমেন্টেশন পদ্ধতি (Implementation Approaches)
প্রায়োরিটি কিউ কয়েকটি পদ্ধতিতে তৈরি করা যায়, যার টাইম কমপ্লেক্সিটি ভিন্ন ভিন্ন হয়:
| Approach | Insert | Extract Max/Min | Peek |
|---|---|---|---|
| Unsorted Array | O(1) | O(n) | O(n) |
| Sorted Array | O(n) | O(1) | O(1) |
| Binary Heap | O(log n) | O(log n) | O(1) |
5. ব্যবহারের ক্ষেত্র (Applications)
- Dijkstra's Algorithm: গ্রাফের শর্টেস্ট পাথ খুঁজে বের করতে।
- Huffman Coding: ডেটা কম্প্রেশন বা জিপ ফাইল তৈরিতে।
- Prim's MST: মিনিমাম স্প্যানিং ট্রি তৈরিতে।
- OS Scheduling: প্রায়োরিটি অনুযায়ী প্রসেস রান করার জন্য।
- Interrupt Handling: সিস্টেম ইন্টারাপ্ট ম্যানেজ করতে।
📊 কমপ্লেক্সিটি অ্যানালাইসিস (General Complexity)
| Operation | Time Complexity (Binary Heap) |
|---|---|
| Insertion | O(log n) |
| Deletion | O(log n) |
| Peek | O(1) |
| Heapify | O(n) |
IMPORTANT
প্রায়োরিটি কিউয়ের জন্য Binary Heap সবচেয়ে জনপ্রিয় কারণ এটি ইনসারশন এবং ডিলিশন উভয় ক্ষেত্রেই লোগারিথমিক টাইম (O(log n)) গ্যারান্টি দেয়।
TIP
জাভাতে PriorityQueue ক্লাস এবং পাইথনে heapq মডিউল ব্যবহার করে সরাসরি প্রায়োরিটি কিউ ব্যবহার করা যায়।