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.


#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;
}
Creative Commons License
This work by Khushman Patel is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.

No comments:

Post a Comment