Question

Can anyone help me write a simple code for this problem in C++?

Generate N>10 random values from 1 to 100 using a uniform probability distribution. N is entered by the user. The first 5 values are put into nodes and added to a priority queue based on their value. Each node also contains a list of values. After the first 5 are inserted into the priority queue the rest of the values are added to the lists with the initial node being the delimiter as the maximum value. This defines an interval from previous node to that value. The range for the first value is 1 to is value Display the contents of the Priority Queue as below: For example if the values were 5, 55, 22, 14, 98, 23, 99, 40, 7, 55, 25, 9, 66 The PQueue would have interval nodes 5, 14, 22, 55, 98 the entire contents would be l values greater than 5 but <= 14)) Node 5 has NO entries Node 14 has values 7,9 Node 22 has NO values Node 55 has value 23, 55 Node 98 has value 66 The value 99 does not appear since it does fall within any of the intervals

Answer 1

The code is given below. The explanation has been comment out through out the code. If still you have any doubts please let me know.

Code:

#include<iostream>

#include<vector>

#include<queue>

#include<random>

using namespace std;

//a class that will store the key and a list of its childs

class myNode{

public:

int key;

vector<int> values;

myNode(){

}

myNode(int k){

key = k;

}

//add value to vector

void pushValue(int val){

values.push_back(val);

}

};

//comparator

class compar {

public:

bool operator() (myNode* const& lhs, myNode* const& rhs) {

return lhs->key > rhs->key;

}

};

int main(){

//create a priority queue that store class myNode

priority_queue<myNode *, vector<myNode*>, compar> PQueue;

//get n

int n;

cout<<"Please enter the value of n(Greater than 10): ";

cin>>n;

//check if n is greate than 10 . if it is not then exit

if(n <= 10){

cout<<"Entered values is not greater than 10\n";

return 0;

}

//create randomised numbers;

int arr[n];

//seed random value generator

srand(time(0));

for(int i = 0; i < n; i++){

arr[i] = 1 + rand()%100; //number from 1 to 100

}

//insert first five elements in PQ

//create arr of five nodes

myNode mn[5];

for(int i = 0; i < 5; i++){

mn[i] = myNode(arr[i]);

PQueue.push(&mn[i]);

}

//create a second priority quese to store the nodes

priority_queue<myNode* , vector<myNode*>, compar> PQueue2;

//insert remainig items

for(int i = 5; i < n; i++){

//find node

while(!PQueue.empty() && PQueue.top()->key < arr[i]){

//insert in second priority queue

PQueue2.push(PQueue.top());

PQueue.pop();

}

//if PQueue is not empty and the key to the top node

if(!PQueue.empty()){

PQueue.top()->pushValue(arr[i]);

}

//Add values back to PQueue

while(!PQueue2.empty()){

//insert in second priority queue

PQueue.push(PQueue2.top());

PQueue2.pop();

}

}

//Display all the nodes;

for(int i = 0; i < 5; i++){

//get minimum node

myNode t = *PQueue.top();

//print the key

cout<<"Node "<<t.key<<" has ";

//if empty vector then print NO values

if(t.values.size() == 0){

cout<<"NO values\n";

}

else{

//print all values.

cout<<"values ";

for(auto k : t.values){

cout<<k<<",";

}

cout<<endl;

}

//remove this element

PQueue.pop();

}

}

Code Screenshot:

Output: