C++ STL :: priority_queue

প্রায়োরিটি কিউঃ

সব ডাটা-স্ট্রাকচারই যে ধোয়া তুলসি পাতা, এইটা বলা যায় না, বিশেষতঃ যখন “জোর যার মুল্লুক তার” টাইপের এই ডাটা-স্ট্রাকচারটা প্রায়ই ব্যবহার করতে হয়, C++ STL এর priority_queue, এটা একটা বাইনারি হিপ ডাটা-স্ট্রাকচার (ডিফল্টঃ ম্যাক্স হিপ)। সহজ বাংলায়, হিপ হল এমন একটা ট্রি ডাটা-স্ট্রাকচার যেখানে সবচেয়ে বড় (ম্যাক্স হিপ) বা সবচেয়ে ছোট (মিন হিপ) এলিমেন্টটা সবসময় রুটে থাকবে। তাই, যদি এমন একটা ঘটনা ঘটে যে, একদল লোক লাইন দিছে কাঙ্গালি ভোজে, এমন টাইমে মাস্তান টাইপের এক ফকির আসছে, আর লোকজন ভয় পেয়ে তাকে লাইনের সামনে দাঁড়া করায় দিবে, তখন প্রায়রিটি কিউ ছাড়া উপায় নাই, অর্থাৎ খালি আগে আসলেই হবে না, যথেষ্ট পরিমানে ভাব নিয়ে আসতে হবে।

এইটা খুব সহজেই করা যায়, বার বার চেক করে যে নেক্সট কার প্রায়রিটি বেশি, কিন্তু এইভাবে করাটা আন-এফিসিয়েন্ট, তার চেয়ে হিপের মত একটা ট্রি ডাটা-স্ট্রাকচার ব্যবহার করে অনেক কম সময়ে এই কাজ করা যায়, আর সেই কাজটাকে আর সহজ করে দেওয়ার জন্যই আছে priority_queue, queue এর মত এটাও একটা অ্যাডাপ্টার ক্লাস, তার মানে হল, যে সব STL কন্টেইনার front(), push_back(), pop_back() এই অ্যাকসেস দেয়, তাদেরকে priority_queue এর ইন্টারনাল কন্টেইনার হিসাবে ব্যবহার করা যাবে। আর এটা ব্যবহার করতে চাইলে std <queue> হেডারটা প্রোগ্রামে ইনক্লুড করতে হবেঃ

#include <queue>
using namespace std;

কনস্ট্রাকশনঃ

priority_queue বেশ কয়েকভাবে বানানো যায়, বাই ডিফল্ট এটা ম্যাক্স হিপ ইম্পলিমেন্ট করে আর এলিমেন্ট কম্পেয়ার (ছোট-বড় বুঝার জন্য) করার জন্য <queue> এর less<type_t> ক্লাস ব্যাবহার করে। চাইলে এটাকে অন্য কোন কন্টেইনার যেমন vector কে ইন্টারনাল কন্টেইনার হিসাবে ডিফাইন করে দেওয়া যায়, আর বিল্ট ইন বা ওভারলোডেড টেমপ্লেট টাইপ ছাড়াও এটা বানানো যায়, সেক্ষেত্রে ডাটার নিজের ডিফল্ট কম্পেয়ারিজন ক্লাস ব্যবহার করতে হবেঃ < কে ওভারলোড করে, অথবা এক্সপ্লিসিট কম্পেয়ারিজন ক্লাসে () কে ওভারলোড করে। আর, মিন হিপ বানানোও সহজ, <queue> এ ডিফাইন করা greater<type_t> ক্লাস ব্যবহার করে খুব সহজেই করা যায়। যেমনঃ

// constructing priority queues
#include <iostream>
#include <queue>
using namespace std;

class mycomparison {
	bool reverse;
public:
	mycomparison(const bool& revparam=false) { reverse = revparam; }
	bool operator() (const int& lhs, const int&rhs) const {
		if (reverse) return (lhs>rhs);
		else return (lhs<rhs);
	}
};

int main () {
	int myints[]= {10,60,50,20};
	
	// default construction
	priority_queue<int> first;
	priority_queue<int> second (myints,myints+3);
	
	// using greater<> to create min heap
	priority_queue< int, vector<int>, greater<int> > third (myints,myints+3);
	
	// using "mycomparison" comparison class
	priority_queue< int, vector<int>, mycomparison > fourth;
	
	typedef priority_queue<int,vector<int>,mycomparison> mypq_type;
	mypq_type fifth (mycomparison());
	mypq_type sixth (mycomparison(true));
	
	return 0;
}

কমপ্লেক্সিটিঃ ইনিশিয়াল এলিমেন্টের সাপেক্ষে লিনিয়ার, ইনিশিয়ার এলিমেন্ট অ্যাসাইন না করলে কন্সট্যান্ট।

পুশ, পপ, টপঃ

priority_queue এর এলিমেন্ট কে অ্যাকসেস করার জন্য ৩ টা ফাংশন ডিফাইন করা আছে, push(), pop() আর top(). কিউতে কোন এলিমেন্ট অ্যাড করতে চাইলে push() ফাংশনটা ব্যবহার করতে হয়, top() হিপের বর্তমান রুটকে রিটার্ন করে, আর pop() সেটা ট্রি থেকে ডিলিট করে। অর্থাৎ top() আর pop() একত্রে ম্যাক্স হিপের জন্য extract_max() আর মিন হিপের জন্য extract_min() [see: Introduction To Algorithms — CLRS — MIT Press] এর কাজ করে। নিচে উদাহরণ দেওয়া হলঃ

// priority_queue::push/pop/top
#include <iostream>
#include <queue>
#include <ctime>
#include <cstdlib>
using namespace std;

int main () {
	priority_queue<int> mypq;
	srand(time(NULL));
	
	cout << "Pushing some random values...\n";
	for(int n, i = 0; i < 10; i++) {
		n = rand();
		cout << " " << n;
		mypq.push(n);
	}
	cout << endl;
	
	cout << "Popping out elements...\n";
	while (!mypq.empty()) {
		cout << " " << mypq.top();
		mypq.pop();
	}
	cout << endl;
	return 0;
}

কমপ্লেক্সিটিঃ push() লগারিদমিক, top() কন্সট্যান্ট, কিন্তু pop() লগারিদমিক।

কিউ এর সাইজ চেক করাঃ

priority_queue এর বর্তমান এলিমেন্ট কতগুলা আছে বা, কিউ খালি কিনা এটা টেস্ট করার জন্য ২ টা ফাংশন ডিফাইন করা আছে, size() আর empty(). কিউ থেকে top() আর pop() ব্যবহার করার আগে অবশ্যই কিউ খালি কিনা চেক করা উচিৎ, তা না হলে রান টাইম এরর জেনারেট হতে পারে। আর, কিউ খালি কিনা এটা empty() মেথড দিয়েই চেক করা উচিত, soze()==0 দিয়ে নয়। STL এর সব কন্টেইনার ক্লাসেই এদের ব্যবহার একি রকমঃ

// priority_queue ::size/empty
#include <iostream>
#include <queue>
using namespace std;

int main () {
	priority_queue<int> myints;
	cout << "0. size: " << (int) myints.size() << endl;
	
	for (int i=0; i<10; i++) myints.push(i);
	cout << "1. size: " << (int) myints.size() << endl;
	
	myints.pop();
	cout << "2. size: " << (int) myints.size() << endl;
	
	while(!myints.empty()) myints.pop();
	cout << "3. size: " << (int) myints.size() << endl;
	
	return 0;
}

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

ব্যবহারঃ

বাইনারি হিপ তৈরিতে, ডায়াকস্ট্রা আর প্রিম অ্যালগরিদমে ব্যবহার করা হয়, টেমপ্লেট ক্লাস হওয়ায় যে কোন ডাটা টাইপের জন্য খুব দ্রুত কোড ইমপ্লিমেন্ট করা যায়।

বিস্তারিতঃ http://www.cplusplus.com/reference/stl/priority_queue/

About these ads
  1. সাদ বিন কাদের
    অগাষ্ট 19, 2010 at 9:16 অপরাহ্ন

    দাদা। পড়ে মজা পেলুম। তাই ধন্যবাদ না দিয়ে পারলুম না। শুভ কামনা।

  2. অগাষ্ট 19, 2010 at 9:27 অপরাহ্ন

    ধন্যবাদ সাদ মামা…

  1. অগাষ্ট 19, 2010 at 3:59 অপরাহ্ন

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / পরিবর্তন )

Twitter picture

You are commenting using your Twitter account. Log Out / পরিবর্তন )

Facebook photo

You are commenting using your Facebook account. Log Out / পরিবর্তন )

Google+ photo

You are commenting using your Google+ account. Log Out / পরিবর্তন )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 49 other followers

%d bloggers like this: