একটি প্রায়োরিটি কিউ (Priority Queue) হল একটি কিউ (queue) টাইপ যেখানে এলিমেন্টগুলো তাদের অ্যাসাইন করা প্রায়োরিটি (priority) অনুযায়ী ইনসার্ট (insert) বা ডিলিট (delete) করা হয়। প্রায়োরিটি হল একটি ইন্টিজার ভ্যালু যা ০-১০ এর মধ্যে থাকতে পারে, যেখানে ০ হাইএস্ট প্রায়োরিটি (highest priority) এবং ১০ লোয়েস্ট প্রায়োরিটি (lowest priority) নির্দেশ করে। প্রায়োরিটি কিউ ইমপ্লিমেন্ট করার জন্য দুটি রুল মেনে চলা হয়:
- হাইএস্ট প্রায়োরিটি ওয়ালা ডেটা বা এলিমেন্ট লোয়েস্ট প্রায়োরিটি ওয়ালা ডেটা বা এলিমেন্টের আগে এক্সিকিউট হবে।
- যদি দুটি এলিমেন্টের প্রায়োরিটি একই হয়, তবে সেগুলো লিস্টে যোগ হওয়ার ক্রম অনুযায়ী এক্সিকিউট হবে।
প্রায়োরিটি কিউ ইমপ্লিমেন্ট করার জন্য একাধিক ডেটা স্ট্রাকচার উপলব্ধ যেমন স্ট্যাক (Stack), কিউ (Queue) এবং লিংকড লিস্ট (Linked List)। এই আর্টিকেলে কিউ ডেটা স্ট্রাকচার ব্যাখ্যা করা হয়েছে। প্রায়োরিটি কিউ ইমপ্লিমেন্ট করার দুটি পদ্ধতি রয়েছে:
- একক অ্যারেতে একাধিক প্রায়োরিটির জন্য কিউ মেইনটেইন করা (Maintain queue for multiple priorities in a single array)
প্রায়োরিটি কিউ ইমপ্লিমেন্ট করার একটি পদ্ধতি হলো প্রতিটি প্রায়োরিটির জন্য একটি কিউ মেইনটেইন করা। আমরা এই একাধিক কিউগুলো একটি সিঙ্গেল অ্যারেতে স্টোর করতে পারি যেখানে প্রতিটি কিউ-এর দুটি পয়েন্টার থাকবে: Front এবং Rear। কিউ-তে Front পয়েন্টার এলিমেন্ট ইনসার্ট করতে ব্যবহৃত হয় এবং এলিমেন্ট ইনসার্ট হলে এটি ১ বাড়ে। আরেকটি পয়েন্টার Rear যা কিউ থেকে এলিমেন্ট ডিলিট বা রিমুভ করতে ব্যবহৃত হয় এবং এলিমেন্ট রিমুভ হলে এটি ১ কমে। akhirnya, দুটি পয়েন্টারের পজিশন থেকে কিউ-তে এলিমেন্টের সংখ্যাও বের করা যায়।
- এই রিপ্রেজেন্টেশনে, নতুন এলিমেন্ট ইনসার্ট করার জন্য পয়েন্টার শিফ্ট (shift) করতে হয় যা টাইম এবং স্পেস দুটোই কমপ্লেক্স করে দেয়।
- একক অ্যারেতে প্রতিটি প্রায়োরিটির জন্য আলাদা কিউ মেইনটেইন করা (Maintain queue for each priority in a single array)
এই মেথডে আমরা প্রতিটি এলিমেন্টের জন্য আলাদা অ্যারে তৈরি করি। প্রতিটি কিউ সার্কুলার অ্যারে (circular array) হিসেবে ইমপ্লিমেন্ট করা হয় এবং দুটি পয়েন্টার ভেরিয়েবল থাকে: Front এবং Rear। দেয়া প্রায়োরিটি নম্বরের এলিমেন্টটি সংশ্লিষ্ট কিউতে ইনসার্ট হয়। একইভাবে, যদি কিউ থেকে এলিমেন্ট ডিলিট করতে চাই, তবে সেটি হাইএস্ট প্রায়োরিটি কিউ থেকে হতে হবে। লোয়েস্ট প্রায়োরিটি ইন্টিজার হাইএস্ট প্রায়োরিটি নির্দেশ করে (০)।
নোট (Note) − যদি প্রতিটি কিউর সাইজ একই হয়, তবে একাধিক वन-ডাইমেনশনাল অ্যারে বানানোর বদলে একটি সিঙ্গেল টু-ডাইমেনশনাল অ্যারে (two-dimensional array) তৈরি করা যায়।
প্রায়োরিটি কিউ-তে ইনসার্ট অপারেশন এর Алগরিদম (Algorithm for Insert Operation In priority queue)
insert(queue, data, priority)
If (queue->Rear[priority] = MAX-1 AND queue->Front[priority] = 0) OR (queue->Rear[priority] + 1 = queue->Front[priority])
Print Overflow
End
IF queue->Rear[priority - 1] = MAX-1
Set queue->Rear[priority - 1] = 0
Else
Set queue->Rear[priority] = queue->Rear[priority - 1] + 1
End
Set queue->CQueue[priority - 1][queue->Rear[priority - 1]] = data
IF queue->Front[priority - 1] = -1
Set queue->Front[priority - 1] = 0
End
প্রায়োরিটি কিউ-তে ডিলিট অপারেশন এর Алগরিদম (Algorithm for Delete Operation In priority queue)
delete(queue)
Set flag = 0, priority = 0
While priority <= MAX-1
IF NOT queue->Front[priority] = -1
Set flag = 1
Set value = queue->CQueue[priority][queue->Front[priority]]
IF queue->Front[priority] = queue->Rear[priority]
Set queue->Front[priority] = queue->Rear[priority] = -1
Else
IF queue->Front[priority] = MAX-1
Set queue->Front[priority] = 0
Else
Set queue->Front[priority] = queue->Front[priority] + 1
End
End
Break
End
Set priority = priority + 1
End
If flag = 0
Print underflow
Else
Return value
End
ব্যাখ্যা: প্রায়োরিটি কিউ একটি অ্যাবস্ট্রাক্ট ডেটা টাইপ (ADT)। C++-এ STL-র priority_queue কন্টেইনার এই কাজটি বিল্ট-ইনভাবে করে। C-তে ম্যানুয়ালি ইমপ্লিমেন্ট করতে হয়। উপরের অ্যালগরিদমগুলো সার্কুলার কিউ ভিত্তিক ইমপ্লিমেন্টেশন দেখিয়েছে।
