Heap Priority Queue C data file httppastebincomvAxJBREE I d

Heap Priority Queue - C++

data file: http://pastebin.com/vAxJBREE

I deal with my customers on a first come first serve bases. I also rank my customers by their request based on a secret ranking procedure (you know, stuff like how fast they pay, the number of tickets they order, the type of tickets they order, how often they order etc etc the secret part). Each ticket packet request is assigned a ranking number or a priority. The bigger the number, the earlier request is process. Equal numbered requests are handled on a FIFO. Since this needs to be a rather fast process, I need a rather fast data structure for adding fetching and deleting request, so we are testing and trying out the ‘priority heap’ data structure to see how well it works. Your job is to implement the Priority Heap only.

I have an input file of data to test your program. The file name is ‘HeapPriortyNbrs.dat’. The input format is ‘idNbr-priority’.   Ex   135-3 or 292-13. One input per line. Second value is priority.

Output: After reading in 100 requests, print out (process) the first 20 request and delete 50 request from the heap.
             Read in the next 100 request and print out (process) the first 30 requests and delete 50 request them
            Read in the rest of the request and print out (pricess) the first 40 request and delete them.

Note: Don’t print the heap output down the page but across the page. Print the priority first followed by the ID number. Make sure equality priorities are handle FCFS

Solution

# include<iostream>
# include<vector> //Header file for vector
# include<fstream> //header file for ifstream
# include<sstream> //header file for stringstream
# include<queue> //Header file for priority queue
# include<string> // Header file for string
# include<algorithm> //Header file for heap.push() adding element into priority queue

using namespace std;

/*function object(functor) implemented using class
by using class or struct that contains function that takes two class objects as arguments and returns desired comparison
*/
class CompareDist
{
public:
bool operator()(pair<int,int> n1,pair<int,int> n2) {
return n1.second<n2.second;
}
};
int main()
{
int arr[2];
ifstream inFile;
string line;

typedef pair<int, int> P;

/*
Below is the priority queue which is having input as pair of integers and CompareDist is functor which compares second
argument of vector and sort according to that.
*/
std::priority_queue<P, std::vector<P>, CompareDist> max_heap;

inFile.open(\"HeapPriortyNbrs.dat\"); //Reading input file

cout<<\"After Reading 100 requests, print out(process) the first 20 request and delete 50 requests from heap\"<<endl;
//Reading 100 requests
for(int j=0;j<100;j++)
{
std::getline(inFile,line);
std::stringstream ss(line);
int i=0,val;
while(ss >> val)
{
arr[i] = val;
i++;
if(ss.peek() == \'-\')
ss.ignore();
}
max_heap.push(std::make_pair(arr[0],arr[1]));
}
//printing first 20 request
for(int j=0;j<20;j++)
{
cout<<max_heap.top().second<<\" : \"<<max_heap.top().first<<\"\\t\";
max_heap.pop();
}
//delete 50 requests
for(int j=0;j<30;j++)
max_heap.pop();

cout <<endl;

cout<<\"After Reading 100 requests, print out(process) the first 30 request and delete 50 requests from heap\"<<endl;
//reading 100 request
for(int j=0;j<100;j++)
{
std::getline(inFile,line);
std::stringstream ss(line);
int i=0,val;
while(ss >> val)
{
arr[i] = val;
i++;
if(ss.peek() == \'-\')
ss.ignore();
}
max_heap.push(std::make_pair(arr[0],arr[1]));
}
//prints first 30 request
for(int j=0;j<30;j++)
{
cout<<max_heap.top().second<<\" : \"<<max_heap.top().first<<\"\\t\";
max_heap.pop();
}
//delete 50 request
for(int j=0;j<20;j++)
max_heap.pop();

cout<<endl;
cout<<\"Read in the rest of the request and print out(process) the first 40 request and delete them\"<<endl;
//read rest of the lines
while(getline(inFile,line))
{
std::stringstream ss(line);
int i=0,val;
while(ss >> val)
{
arr[i] = val;
i++;
if(ss.peek() == \'-\')
ss.ignore();
}
max_heap.push(std::make_pair(arr[0],arr[1]));

}
//print 40 request and delete them
for(int j=0;j<40;j++)
{
cout<<max_heap.top().second<<\" : \"<<max_heap.top().first<<\"\\t\";
max_heap.pop();
}

}