#include#include #include #include using namespace std; struct node { int priority; int data; }; bool operator < ( node n1, node n2 ) { if( n1.priority < n2.priority ) return true; return false; } int find( priority_queue< node > q, int data ) { node n; int i = 0; while( !q.empty() ) { i++; n = q.top(); q.pop(); if( n.data == data ) return i; } return -1; } void display( priority_queue< node > q ) { while( !q.empty() ) { cout << "Priority: " << q.top().priority << "\tData: " << q.top().data << "\n"; q.pop(); } } void empty( priority_queue< node > &q ) { while ( !q.empty() ) q.pop(); } bool change_priority( priority_queue< node > &q, int index, int new_priority ) { priority_queue< node > new_q; node n; bool flag = true; while( !q.empty() ) { n = q.top(); q.pop(); if( n.priority == index ) { n.priority = new_priority; flag = true; } new_q.push( n ); } q = new_q; return flag; } int main( int argc, char **args ) { priority_queue< node > q; node ntemp; int n; freopen( args[1], "r", stdin ); cin >> n; cout << "n: " << n << "\n"; cout << "Input:\n"; for( int i = 0; i < n; i++ ) { scanf( "%d %d", &ntemp.priority, &ntemp.data ); cout << "Pri: " << ntemp.priority << "\tData: " << ntemp.data << "\n"; q.push( ntemp ); } cout << "Display:\n"; display( q ); cout << "Find 6324: " << find( q, 6324 ) << "\n"; cout << "Find 3: " << find( q, 3 ) << "\n"; cout << "Displayed if priority changed.\n"; if( change_priority( q, 24, 332 ) ) { display( q ); } return 0; }
Tuesday, June 28, 2011
Max Priority Queue
This includes a maximum priority queue implementation using a heap, and a map C++ STL. It gives atleast O(log(n)) time for every operation.
This work by Khushman Patel is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Labels:
c++,
max priority queue,
maximum priority queue,
priority queue,
queue
Subscribe to:
Comments (Atom)