প্রায়োরিটি কিউ একটি খুবই জনপ্রিয় ডাটা স্ট্রাকচার । এটি মূলত ম্যাক্স হিপ এর একটি ইমপ্লিমেন্টেশন ।
আমরা ইতোমধ্যে “প্রায়োরিটি” এবং “ম্যাক্স” এই শব্দ দুইটিকে আমাদের লেখার শুরুতে উল্লেখ করেছি । কারণ এই দুটোর মিশ্রণেই প্রায়োরিটি কিউ কাজ করে । “হিপ” ও একটি ডাটা স্ট্রাকচার, কিন্তু হিপ এর বর্ণণায় আমরা এখন যাব না । প্রায়োরিটি কিউ মূলত কোন জিনিসকে অটোমেটিকালি প্রায়োরিটি দিয়ে সর্ট করে । মানে আমরা যদি প্রায়োরিটি কিউতে কোন কিছু ইনসার্ট করতে থাকি, তাহলে আমাদের এই প্রায়োরিট কিউ যার “প্রায়োরিটি” বেশি তাকে আগে রাখতে থাকবে ।
প্রায়োরিটি কিউ নিয়ে আমাদের এই সাইটে খুব সুন্দর একটি লেখা আছে, মুন্তাসির ওয়াহেদ এর । প্রায়োরিটি কিউ কীভাবে কাজ করে তা কিছুই জেনে না থাকলে এই লেখাটি দেখে আসার অনুরোধ রইল ।
লেখাটির লিঙ্কঃhttp://shoshikkha.com/archives/526
এখন, আমরা প্রায়োরিটি কিউ নিয়ে কিছু অ্যাডভান্স কাজ করব । আমরা যদি লেখাটি পড়ে থাকি তাহলে আমাদের অনেকেরই মনে হবে, “প্রায়োরিট কিউ সবসময় বড় মানগুলো কে সামনে রাখে আর ছোট মানগুলোকে পেছনে রাখে। আর এটা একটা অলটাইম সর্টেড কিউ ।” পরের কথাটি সত্য হলে ও প্রথম কথাটিকে একটু হেলাফেলা করা যায় । আমরা ইচ্ছা করলে ছোট মানগুলোকে ও সামনে রাখতে পারি । আর এর জন্য আমাদের কম্পেরিজন (comparison ) ওপারেটর গুলোর কাজে পরিবর্তন আনতে হবে । কম্পেরিজন (comparison) ওপারেটর বলতে আমরা এখানে বুঝাচ্ছি, “, <” এবং ” >” কে । আমরা যেহেতু ওপারেটর এর কাজে পরিবর্তন এনে আমাদের প্রায়োরিটি কিউ এর কাজ নিজের দরকার মত চেঞ্জ করছি, এই “অপারেটর এই কাজ পরিবর্তন করা” এটিকেই বলা হয় ওপারেটর ওভারলোডিং করা ।
তো ওপারেটর ওভারলোডিং এর কাজ আমরা কীভাবে চেঞ্জ করতে পারি ।
আমরা যেহেতু নরমালি একটা জিনিসের স্বভাবসুলভ আচরণ পরিবর্তন করছি , আমাদের একটি আলাদা ফাংশন লিখতে হবে । যেটাকে আমরা boolean ডাটা টাইপের রাখতে পারি । আর যেহেতু ওপারেটর এর কাজ চেঞ্জ করছি তাই এর ডাটা টাইপ হবে ,
bool operator< (.......)
এখানে আমরা “<” ব্যবহার করেছি, প্রায়োরিটি কিউ এই অপারেটরে কাজ করে । আর ব্রেকেট এর ভেতরে আমরা রাখব কোন ধরণের প্রায়োরিট কিউ নিয়ে আমরা কাজ করছি ।
যেমন যদি আমরা স্ট্রাকচার নিয়ে কাজ করি , তাহলে আমরা আমাদের সিনটেক্স এভাবে লিখব ।
struct node
{
int identity;
};
bool operator<(const node &a, const node &b) {
if(a.identity > b.identity) return true; // এখানে আমরা ছোটগুলোকে আগে রাখছি ।
else return false;
}
priority_queue < struct node > pq;
এখানে আমরা নরমালি প্রথমে আমাদের স্ট্রাকচার ডিফাইন করেছি, প্রায়োরিটি কিউ কোন ধরণের জিনিস নিয়ে কাজ করবে তা ডিফাইন করেছি আর আমাদের প্রায়োরিটি কিউ এর একটা নাম দিয়েছি (pq) . আর তারপরে আমাদের ওপারেটর এর কাজ ডিফাইন করেছি । এখন আমরা যদি বড়গুলোকে আগে রাখতে চাইতাম তাহলে কী করতাম, শুধুমাত্র (a.identity < b.identity) হলে ট্রু রিটার্ন করতাম অন্যথায় ফলস ।
এখানে আমরা & use করি কারণ আমরা এখানে মানগুলোর রেফারেন্স বা শুধু মান নিয়ে কাজ করি আর const use করি যাতে “মানগুলো” শুধু যায়, কমপ্লিটলি চেঞ্জ যেন না হয় । অর্থ, আমরা শুধুমাত্র মান নিয়ে কাজ করি কিন্তু সম্পূর্ণভাবে পরিবর্তন করি না ।
এভাবে করেই আমরা আমাদের ওপারেটর এর কাজ ঠিক করে প্রায়োরিট কিউ এর কাজ হ্যাণ্ডেল করতে পারব । প্রায়োরিট কিউ এর অনেক বড় একটা ইমপ্লিমেন্টশন লাগে ডায়াস্কট্রা প্রবলেম সলভিং এ, যেখানে আমরা ওপারেটর ওভারলোডিং করে সোর্স এর কাছের নোডগুলোকে নিয়ে আগে কাজ করি ।
এই ব্যাপারে আরো জানতে আমরা নিচের লেখাটিও পড়তে পারি,
Codechef: Operator overloading in STL
কৃতজ্ঞতা স্বীকারঃ শাহাদাত হোসেন শাহীন ।