প্রায়রিটি কিউ হল একটি অ্যাবসট্রাক্ট ডেটা টাইপ যা প্রায়োরিটাইজড উপাদানগুলোর সংগ্রহ সংরক্ষণ করে এবং উপাদান ইনসারশন এবং ডিলিশন তাদের প্রায়োরিটি অনুযায়ী সাপোর্ট করে, অর্থাৎ সর্বোচ্চ প্রায়োরিটিওয়ালা উপাদান যেকোনো সময় সরানো যাবে। প্রায়রিটি কিউ স্ট্যাক, কিউ, লিস্টের মতো লিনিয়ার ফ্যাশনে উপাদান সংরক্ষণ করে না তাদের লোকেশন অনুযায়ী। প্রায়রিটি কিউ ADT উপাদানগুলোর প্রায়োরিটি অনুযায়ী সংরক্ষণ করে।
প্রায়রিটি কিউ নিচের ফাংশনগুলো সাপোর্ট করে:
- Size() - প্রায়রিটি কিউর আকার বের করতে ব্যবহৃত হয় কারণ এটি উপাদান সংখ্যা রিটার্ন করে।
- Empty() - প্রায়রিটি কিউ খালি থাকলে true এবং অন্যথায় false রিটার্ন করে।
- Insert(element) - প্রায়রিটি কিউতে নতুন উপাদান ইনসার্ট করতে ব্যবহৃত হয়।
- Min() - সবচেয়ে ছোট আসোসিয়েটেড কি ভ্যালু ওয়ালা উপাদান রিটার্ন করে এবং প্রায়রিটি কিউ খালি থাকলে এরর মেসেজ দেখায়।
- removeMin() - min() ফাংশন দিয়ে রেফারেন্স করা উপাদান সরিয়ে দেয়।
কাজ হল C++-এ পেয়ারের প্রায়রিটি কিউ বাস্তবায়ন করা যেটি প্রথম উপাদান অনুযায়ী অর্ডার্ড।
আমরা সমস্যাটি হিপের অনুরূপ সমাধান করতে পারি, দুটি পদ্ধতি আছে:
- ম্যাক্স প্রায়রিটি বা ম্যাক্স হিপ
- মিন প্রায়রিটি বা মিন হিপ
হিপ হল একটি ট্রি স্ট্রাকচার যেখানে নোডগুলো নির্দিষ্ট ক্রমে সাজানো থাকে। হিপ দুই ধরনের: মিন হিপ এবং ম্যাক্স হিপ। মিন হিপে রুট নোড বা পেরেন্ট নোড তার চাইল্ড নোডের চেয়ে ছোট হয়, আর ম্যাক্স হিপে রুট নোড বা পেরেন্ট নোড তার চাইল্ড নোডের চেয়ে বড় হয়।
উদাহরণ
Input: priorityq.push(make_pair(18, 200)) Input: priorityq.push(make_pair(18, 200)) priorityq.push(make_pair(29, 100)) priorityq.push(make_pair(11, 400)) Output: 29 100 Input: priorityq.push(make_pair(10, 200)) priorityq.push(make_pair(20, 100)) priorityq.push(make_pair(19, 400)) Output: 20 100 Through Max priority (Max heap)
অ্যালগরিদম
Start
Step 1-> In main function()
Define priority_queue> priorityq
Call priorityq.push(make_pair(18, 200))
Call priorityq.push(make_pair(29, 100))
Call priorityq.push(make_pair(11, 400))
Set pair top = priorityq.top()
Print top.first and top.second
Stop
উদাহরণ (Max Heap)
#include <bits/stdc++.h>
using namespace std;
int main() {
priority_queue<pair<int, int>> priorityq;
priorityq.push(make_pair(18, 200));
priorityq.push(make_pair(29, 100));
priorityq.push(make_pair(11, 400));
pair<int, int> top = priorityq.top();
cout << top.first << " " << top.second;
return 0;
}
আউটপুট
29 100
মিন প্রায়রিটি (Min Heap) দিয়ে
অ্যালগরিদম
Start
Step 1-> In main function()
Define priority_queue> priorityq
Call pq.push(make_pair(10, 200))
Call pq.push(make_pair(20, 100))
Call pq.push(make_pair(15, 400))
Set pair top = pq.top()
Print top.first and top.second
Stop
উদাহরণ (Min Heap)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
int main() {
priority_queue<pi, vector<pi>, greater<pi>> pq;
pq.push(make_pair(10, 200));
pq.push(make_pair(20, 100));
pq.push(make_pair(15, 400));
pair<int, int> top = pq.top();
cout << top.first << " " << top.second;
return 0;
}
আউটপুট
10 200
