May 5, 2012 (last update: Mar 11, 2013)

priority_queue

look at this first :
http://www.cplusplus.com/reference/stl/priority_queue/

now we want to define a priority queue that enable us to Add element to priority queue with custom KEY.

Define Priority Queue

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142`` ``````#include using namespace std; template class PriorityQueue { private: vector Key; vector element; vector::iterator it; void insert(const T &value,const int &key ,const int l ,const int h) { if( h<=l ) { if(Key.at(l)>= key ) { it = element.begin(); //it++; element.insert(it+l,value); it = Key.begin(); //it++; Key.insert(it+l,key); } else { it = element.begin(); it++; element.insert(it+l,value); it = Key.begin(); it++; Key.insert(it+l,key); } } else { int mid = ( l + h ) / 2 ; if ( Key.at( mid ) == key ) // maybe queue have two element with same Priority { it = element.begin(); //it++; element.insert(it+mid,value); it = Key.begin(); //it++; Key.insert(it+mid,key); } else if( Key.at( mid ) > key ) { insert(value,key,l,mid-1 ); } else if ( Key.at( mid ) < key ) { insert(value,key,mid+1,h ); } } } public: PriorityQueue(const PriorityQueue& Copy) { Key = Copy.Key; element = Copy.element; } PriorityQueue operator=(const PriorityQueue& Copy) { Key = Copy.Key; element = Copy.element; return *this; } PriorityQueue() { } bool empty() { return element.empty(); } int size() { return element.size(); } void push(const T& value ,const int& key) { if(element.empty()) { element.push_back(value); Key.push_back(key); } else { int s= element.size()-1; insert(value,key,0,s); } } T popLowestPriority() { T temp = element.at(0); it = element.begin(); element.erase(it); it = Key.begin(); Key.erase(it); return temp ; } T popHighestPriority() { T temp = element.back(); element.pop_back(); Key.pop_back(); return temp ; } void changePriority(T value , int newKey) { it = element.begin(); int elementSize = element.size(); for( int i = 0 ; i < elementSize ; i++ ) { if( element.at( i ) == value ) { element.erase( it+i); it = Key.begin(); Key.erase(it+i); this->push(value,newKey); } } } }; ``````

Example :

Input:
 ``12345678910111213141516171819202122`` `````` PriorityQueue elem; elem.push(1,7); elem.push(2,1); elem.push(3,9); elem.push(4,3); elem.push(5,6); elem.push(8,6); for( int i = 0 ; !elem.empty() ; i++ ) cout<

Output :
 ``` 2 4 8 5 1 3 ------- 8 2 4 5 1 3 ```

-----
Sincerely yours,
Sohrab Aboozarkhani Fard
B.S. Student,
Department of Computer Science, "Kharazmi" University , Tehran , Iran.