মডিউল ২৩-১ঃ Priority Queue কি?

আজকে আমরা দেখব প্রায়োরিটি কিউ ডাটা স্ট্রাকচার। এটি মূলত একটি কিউ ডাটা স্ট্রাকচার যা প্রায়োরিটি মেইনটেইন করে। কিউ এর মতো প্রায়োরিটি কিউও একটি কিউ বা লাইন মেইনটেইন করে যা FIFO(First In First Out) ফলো করে। এক্সট্রা হিসেবে এখানে একটি প্রায়োরিটি থাকে। যার প্রায়োরিটি বেশি সে পরে আসলেও লাইনে সবার আগে চলে যায়। মনে করি একটি টিকেট কাউন্টার এর লাইনে কিছু সাধারন মানুষ দাড়িয়ে আছে। এখন সেই লাইনের শেষে একজন ভিআইপি পারসন আসল। সে সবার পরে আসছে তাই FIFO অনুযায়ী ভিআইপি লাইনে সবার শেষে থাকার কথা। কিন্তু বর্তমানে লাইনে দাড়িয়ে থাকা সবার মধ্যে ভিআইপি পারসনের প্রায়োরিটি সবচেয়ে বেশি তাই সে লাইনে সবার শুরুতে চলে যাবে। এভাবে প্রায়োরিটি কিউ কাজ করে।

সি++ এ প্রায়োরিটি কিউ দুই রকমের হয়ে থাকে। ম্যাক্সিমাম প্রায়োরিটি কিউ যেখানে বড় সংখ্যার প্রায়োরিটি বেশি থাকে। মিনিমাম প্রায়োরিটি কিউ যেখানে ছোট সংখ্যার প্রায়োরিটি বেশি থাকে।

আমরা একটি ম্যাক্সিমাম প্রায়োরিটি কিউ দেখে নেইঃ

। ১০ । -> ১০ আসলো। । ১০ । ৩ । -> ১০ এর পর ৩ আসলো FIFO এবং প্রায়োরিটি অনুযায়ী ১০ এর পরে গেল। । ১০ । ৫ । ৩ । -> এর পর ৫ আসলো। FIFO অনুযায়ী সবার শেষে যাওয়ার কথা কিন্তু ৫ এর প্রায়োরিটি ৩ এর থেকে বেশি এবং ১০ এর থেকে কম তাই ১০ এবং ৩ এর মাঝে চলে গেল। । ২০ । ১০ । ৫ । ৩ । -> এর পর ২০ আসলো। ২০ এর প্রায়োরিটি সবচেয়ে বেশি তাই ২০ সবার আগে চলে আসলো।

একটি মাক্সিমাম প্রায়োরিটি কিউ এভাবে কাজ করে। এখানে একটি ভেলু ডিলিট ও পুশ করার কমপ্লেক্সিটি O(logN)। এভাবে করে আমরা চাইলে ভেলু সর্টও করে ফেলতে পারি। এই সর্টিং এলগরিদম এর নাম হচ্ছে হিপ সর্ট। যার কমপ্লেক্সিটি O(NlogN)।