Hi, I need help with my C++ code using priority queue. I need to create an array
ID: 3708290 • Letter: H
Question
Hi, I need help with my C++ code using priority queue. I need to create an array based priority queue using max heap. Also, I need to Input the registering clients one by one in the file and enque them one by one into the priority queue. Each client input data will consist of client priority and name. I need to implement the <<cin statements as the code provided for example in my code.
My code:
#include <iostream>
#include<fstream>
#include<string>
using namespace std;
struct RecType
{
int priority;
string name;
};
class pque
{
public:
RecType x[100];
int lastIndex;
RecType userInput;
private:
void maxreheapifyUpward(RecType x[], int lastIndex)
{
int parentIndex;
int childIndex = lastIndex;
while (childIndex > 0)
{
parentIndex = childIndex / 2;
if (x[childIndex].priority <= x[parentIndex].priority)
break;
else
{
swap(x, parentIndex, childIndex);
childIndex = parentIndex;
//maxreheapifyUpward(x,childIndex);
}
}
}
void maxreheapifyDownward(RecType x[], int lastIndex)
{
int parentIndex = 0;
int largeChildIndex;
while (parentIndex < lastIndex)
{
largeChildIndex = findLargeChildIndex(parentIndex, lastIndex);
if (largeChildIndex < 0 || x[largeChildIndex].priority <= x[parentIndex].priority)
break;
else
{
swap(x, parentIndex, largeChildIndex);
parentIndex = largeChildIndex;
//maxreheapifyDownward(x,parentIndex);
}
}
}
int findLargeChildIndex(int parentIndex, int lastIndex)
{
int lChildIndex = (2 * parentIndex) + 1;
int rChildIndex = (2 * parentIndex) + 2;
//case both children exist
if (rChildIndex <= lastIndex && lChildIndex <= lastIndex)
{
if (x[rChildIndex].priority>x[lChildIndex].priority)
return rChildIndex;
else
return lChildIndex;
}
//case only left child exist
else if (lChildIndex <= lastIndex)
{
return lChildIndex;
}
//case both children missing
else
{
return -1;
}
}
public:
pque()
{
lastIndex = -1;
}
void penque(RecType n)
{
lastIndex++;
x[lastIndex] = n;
maxreheapifyUpward(x, lastIndex);
}
RecType pdeque()
{
RecType returnValue = x[0];
x[0] = x[lastIndex];
lastIndex--;
maxreheapifyDownward(x, lastIndex);
return returnValue;
}
void swap(RecType x[], int parentIndex, int childIndex)
{
RecType t;
t = x[parentIndex];
x[parentIndex] = x[childIndex];
x[childIndex] = t;
}
bool isEmpty()
{
if (lastIndex < 0)
return true;
else
return false;
}
};
int main()
{
pque PQ;
ifstream myReadFile;
RecType rt;
myReadFile.open("Grade.txt");
//if (myReadFile.is_open())
while (1)
{
myReadFile >> rt.priority;
if (rt.priority != -1)
{
myReadFile >> rt.name;
PQ.penque(rt);
}
else
break;
}
while (!PQ.isEmpty())
{
rt = PQ.pdeque();
cout << " " << rt.priority << " " << rt.name;
}
cout << endl << endl;
return 0;
}
Example Code To Compare that I need <<cin statements:
CODE For Records
struct RecType
{
int priority;
char name [20];
};
struct NodeType
{
int priority;
char name [20];
NodeType * next;
};
class pque
{
private:
RecType x[100];
int lastIndex;
void maxreheapifyUpward (RecType x [], int lastIndex);
void maxreheapifyDownward (RecType x [], int lastIndex);
int findLargeChildIndex (int parentIndex, int lastIndex);
public:
pque ();
void penque (RecType r);
RecType pdeque ( );
bool isEmpty ( );
};
CODE For Ints
//The code below is for an int heap array.
//Also this code doesn't use a class
//Parts of the code are missing and is so indicated.
//Modify this code so that it is for a record heap array.
//Modify this code so that it is for class
bool isEmpty();
void penque (int x);
int pdeque ( );
void maxreheapifyUpward (int x [], int lastIndex);
void maxreheapifyDownward (int x [], int lastIndex);
int findLargeChildIndex (int parentIndex, int lastIndex);
int lastIndex = -1;
int x[100];
int main()
{
int n;
cout << "input number" << endl;
cin >> n;
while (n>=0)
{
penque(n);
cout << "input number" << endl;
cin >> n;
}
while (!isEmpty())
{
n = pdeque();
cout << n << endl;
}
return 0;
}
bool isEmpty()
{
if (lastIndex < 0)
return true;
else
return false;
}
void penque (int n)
{
lastIndex++;
x[lastIndex]=n;
maxreheapifyUpward(x,lastIndex);
}
int pdeque ( )
{
int returnValue = x[0];
x[0]= x[lastIndex];
lastIndex--;
maxreheapifyDownward(x,lastIndex);
return returnValue;
}
//maxreheapifyUpward
//The code below is for an int heap array.
//Modify this method so that it is for a record heap array.
//Also fill in the unfilled part of the code.
void maxreheapifyUpward (int x [], int lastIndex)
{
int parentIndex;
int childIndex = lastIndex;
while (childIndex > 0 )
{
parentIndex = childIndex/2;
if (x [childIndex] <= x [parentIndex])
break;
else
{
//swap values at child and at parent.
//Update child to parent
childIndex = parentIndex;
}
}
}
//maxreheapifyDownward
//The algorithm below is for an int heap array,
//Modify this method so that it is for a record heap array.
//Also fill in the unfilled part of the code.
void maxreheapifyDownward (int x [], int lastIndex)
{
int parentIndex = 0;
int largeChildIndex;
while (parentIndex < lastIndex)
{
largeChildIndex = findLargeChildIndex (parentIndex, lastIndex);
if (largeChildIndex < 0 || x [largeChildIndex] <= x [parentIndex])
break;
else
{
//swap value at parentIndex with value at largeChildIndex
//update parentIndex
parentIndex = largeChildIndex;
}
}
}
int findLargeChildIndex (int parentIndex, int lastIndex)
{
int lChildIndex = (2 * parentIndex) + 1;
int rChildIndex = (2 * parentIndex) + 2;
//case both children exist
if (rChildIndex <= lastIndex && lChildIndex <= lastIndex)
{
//compare value at rChildIndex and at lChildIndex
//return the index where the value is larger
}
//case only left child exist
else if (lChildIndex <= lastIndex)
{
return lChildIndex;
}
//case both children missing
else
{
return -1;
}
}
Code with a Record As In Assignment
#include <iostream>
using namespace std;
class pque
{
public:
struct RecType
{
int priority;
string name;
};
RecType x[100];
int lastIndex;
RecType userInput;
private:
void maxreheapifyUpward (RecType x [], int lastIndex)
{
int parentIndex;
int childIndex = lastIndex;
while (childIndex > 0 )
{
parentIndex = childIndex/2;
if (x[childIndex].priority <= x[parentIndex].priority)
break;
else
{
///swap values at child and at parent.
RecType tempIndex = x[childIndex];
x[childIndex] = x[parentIndex];
x[parentIndex] = tempIndex;
///Update child to parent
childIndex = parentIndex;
}
}
}
void maxreheapifyDownward (RecType x [], int lastIndex)
{
int parentIndex = 0;
int largeChildIndex;
///cout << "hi maxreheapifyDownward" << endl;
while (parentIndex < lastIndex)
{
///cout << "hi maxreheapifyDownward 2" << endl;
largeChildIndex = findLargeChildIndex (x, parentIndex, lastIndex);
if (largeChildIndex < 0 || x[largeChildIndex].priority <= x [parentIndex].priority)
break;
else
{
///swap value at parentIndex with value at largeChildIndex
RecType temp = x[parentIndex];
x[parentIndex] = x[largeChildIndex];
x[largeChildIndex] = temp;
///update parentIndex
parentIndex = largeChildIndex;
}
}
}
int findLargeChildIndex (RecType x[], int parentIndex, int lastIndex)
{
int lChildIndex = (2 * parentIndex) + 1;
int rChildIndex = (2 * parentIndex) + 2;
//case both children exist
if (rChildIndex <= lastIndex && lChildIndex <= lastIndex)
{
///compare value at rChildIndex and at lChildIndex
///return the index where the value is smaller
if (x[rChildIndex].priority > x[lChildIndex].priority)
{
return rChildIndex;
}
else
{
return lChildIndex;
}
}
///case only left child exist
else if (lChildIndex <= lastIndex)
{
return lChildIndex;
}
///case both children missing
else
{
return -1;
}
}
public:
pque() {lastIndex=-1;}
void penque (int p, string n)
{
lastIndex++;
x[lastIndex].priority = p;
x[lastIndex].name = n;
maxreheapifyUpward(x,lastIndex);
}
RecType pdeque ()
{
RecType returnValue = x[0];
x[0] = x[lastIndex];
lastIndex--;
maxreheapifyDownward(x,lastIndex);
return returnValue;
}
bool isEmpty ()
{
if (lastIndex < 0){return true;}
else{return false;}
}
};
int main()
{
pque recordList;
while (recordList.userInput.priority >= 0)
{
cout << "input number" << endl;
cin >> recordList.userInput.priority;
if (recordList.userInput.priority == -1)
{
break;
}
cout << "input name" << endl;
cin >> recordList.userInput.name;
recordList.penque(recordList.userInput.priority, recordList.userInput.name);
}
while (!recordList.isEmpty())
{
recordList.userInput = recordList.pdeque();
cout << recordList.userInput.priority << " " << recordList.userInput.name << endl;
}
return 0;
}
Input Data
3 Jim
2 Judy
7 Jill
1 Jimmy
10 Joe
4 Jacob
8 Joseph
9 Josephine
5 Jackie
6 John
-1
Output
10 Joe
9 Josephine
8 Joseph
7 Jill
6 John
5 Jackie
4 Jacob
3 Jim
2 Judy
1 Jimmy
Explanation / Answer
#include <iostream>
#include<fstream>
#include<string>
using namespace std;
struct RecType
{
int priority;
string name;
};
class pque
{
public:
RecType x[100];
int lastIndex;
RecType userInput;
private:
void maxreheapifyUpward(RecType x[], int lastIndex)
{
int parentIndex;
int childIndex = lastIndex;
while (childIndex > 0)
{
parentIndex = childIndex / 2;
if (x[childIndex].priority <= x[parentIndex].priority)
break;
else
{
swap(x, parentIndex, childIndex);
childIndex = parentIndex;
//maxreheapifyUpward(x,childIndex);
}
}
}
void maxreheapifyDownward(RecType x[], int lastIndex)
{
int parentIndex = 0;
int largeChildIndex;
while (parentIndex < lastIndex)
{
largeChildIndex = findLargeChildIndex(parentIndex, lastIndex);
if (largeChildIndex < 0 || x[largeChildIndex].priority <= x[parentIndex].priority)
break;
else
{
swap(x, parentIndex, largeChildIndex);
parentIndex = largeChildIndex;
//maxreheapifyDownward(x,parentIndex);
}
}
}
int findLargeChildIndex(int parentIndex, int lastIndex)
{
int lChildIndex = (2 * parentIndex) + 1;
int rChildIndex = (2 * parentIndex) + 2;
//case both children exist
if (rChildIndex <= lastIndex && lChildIndex <= lastIndex)
{
if (x[rChildIndex].priority>x[lChildIndex].priority)
return rChildIndex;
else
return lChildIndex;
}
//case only left child exist
else if (lChildIndex <= lastIndex)
{
return lChildIndex;
}
//case both children missing
else
{
return -1;
}
}
public:
pque()
{
lastIndex = -1;
}
void penque(RecType n)
{
lastIndex++;
x[lastIndex] = n;
maxreheapifyUpward(x, lastIndex);
}
RecType pdeque()
{
RecType returnValue = x[0];
x[0] = x[lastIndex];
lastIndex--;
maxreheapifyDownward(x, lastIndex);
return returnValue;
}
void swap(RecType x[], int parentIndex, int childIndex)
{
RecType t;
t = x[parentIndex];
x[parentIndex] = x[childIndex];
x[childIndex] = t;
}
bool isEmpty()
{
if (lastIndex < 0)
return true;
else
return false;
}
};
int main()
{
pque PQ;
ifstream myReadFile;
RecType rt;
myReadFile.open("Grade.txt");
//if (myReadFile.is_open())
while (1)
{
myReadFile >> rt.priority;
if (rt.priority != -1)
{
myReadFile >> rt.name;
PQ.penque(rt);
}
else
break;
}
while (!PQ.isEmpty())
{
rt = PQ.pdeque();
cout << " " << rt.priority << " " << rt.name;
}
cout << endl << endl;
return 0;
}
Example Code To Compare that I need <<cin statements:
CODE For Records
struct RecType
{
int priority;
char name [20];
};
struct NodeType
{
int priority;
char name [20];
NodeType * next;
};
class pque
{
private:
RecType x[100];
int lastIndex;
void maxreheapifyUpward (RecType x [], int lastIndex);
void maxreheapifyDownward (RecType x [], int lastIndex);
int findLargeChildIndex (int parentIndex, int lastIndex);
public:
pque ();
void penque (RecType r);
RecType pdeque ( );
bool isEmpty ( );
};
CODE For Ints
//The code below is for an int heap array.
//Also this code doesn't use a class
//Parts of the code are missing and is so indicated.
//Modify this code so that it is for a record heap array.
//Modify this code so that it is for class
bool isEmpty();
void penque (int x);
int pdeque ( );
void maxreheapifyUpward (int x [], int lastIndex);
void maxreheapifyDownward (int x [], int lastIndex);
int findLargeChildIndex (int parentIndex, int lastIndex);
int lastIndex = -1;
int x[100];
int main()
{
int n;
cout << "input number" << endl;
cin >> n;
while (n>=0)
{
penque(n);
cout << "input number" << endl;
cin >> n;
}
while (!isEmpty())
{
n = pdeque();
cout << n << endl;
}
return 0;
}
bool isEmpty()
{
if (lastIndex < 0)
return true;
else
return false;
}
void penque (int n)
{
lastIndex++;
x[lastIndex]=n;
maxreheapifyUpward(x,lastIndex);
}
int pdeque ( )
{
int returnValue = x[0];
x[0]= x[lastIndex];
lastIndex--;
maxreheapifyDownward(x,lastIndex);
return returnValue;
}
//maxreheapifyUpward
//The code below is for an int heap array.
//Modify this method so that it is for a record heap array.
//Also fill in the unfilled part of the code.
void maxreheapifyUpward (int x [], int lastIndex)
{
int parentIndex;
int childIndex = lastIndex;
while (childIndex > 0 )
{
parentIndex = childIndex/2;
if (x [childIndex] <= x [parentIndex])
break;
else
{
//swap values at child and at parent.
//Update child to parent
childIndex = parentIndex;
}
}
}
//maxreheapifyDownward
//The algorithm below is for an int heap array,
//Modify this method so that it is for a record heap array.
//Also fill in the unfilled part of the code.
void maxreheapifyDownward (int x [], int lastIndex)
{
int parentIndex = 0;
int largeChildIndex;
while (parentIndex < lastIndex)
{
largeChildIndex = findLargeChildIndex (parentIndex, lastIndex);
if (largeChildIndex < 0 || x [largeChildIndex] <= x [parentIndex])
break;
else
{
//swap value at parentIndex with value at largeChildIndex
//update parentIndex
parentIndex = largeChildIndex;
}
}
}
int findLargeChildIndex (int parentIndex, int lastIndex)
{
int lChildIndex = (2 * parentIndex) + 1;
int rChildIndex = (2 * parentIndex) + 2;
//case both children exist
if (rChildIndex <= lastIndex && lChildIndex <= lastIndex)
{
//compare value at rChildIndex and at lChildIndex
//return the index where the value is larger
}
//case only left child exist
else if (lChildIndex <= lastIndex)
{
return lChildIndex;
}
//case both children missing
else
{
return -1;
}
}
Code with a Record As In Assignment
#include <iostream>
using namespace std;
class pque
{
public:
struct RecType
{
int priority;
string name;
};
RecType x[100];
int lastIndex;
RecType userInput;
private:
void maxreheapifyUpward (RecType x [], int lastIndex)
{
int parentIndex;
int childIndex = lastIndex;
while (childIndex > 0 )
{
parentIndex = childIndex/2;
if (x[childIndex].priority <= x[parentIndex].priority)
break;
else
{
///swap values at child and at parent.
RecType tempIndex = x[childIndex];
x[childIndex] = x[parentIndex];
x[parentIndex] = tempIndex;
///Update child to parent
childIndex = parentIndex;
}
}
}
void maxreheapifyDownward (RecType x [], int lastIndex)
{
int parentIndex = 0;
int largeChildIndex;
///cout << "hi maxreheapifyDownward" << endl;
while (parentIndex < lastIndex)
{
///cout << "hi maxreheapifyDownward 2" << endl;
largeChildIndex = findLargeChildIndex (x, parentIndex, lastIndex);
if (largeChildIndex < 0 || x[largeChildIndex].priority <= x [parentIndex].priority)
break;
else
{
///swap value at parentIndex with value at largeChildIndex
RecType temp = x[parentIndex];
x[parentIndex] = x[largeChildIndex];
x[largeChildIndex] = temp;
///update parentIndex
parentIndex = largeChildIndex;
}
}
}
int findLargeChildIndex (RecType x[], int parentIndex, int lastIndex)
{
int lChildIndex = (2 * parentIndex) + 1;
int rChildIndex = (2 * parentIndex) + 2;
//case both children exist
if (rChildIndex <= lastIndex && lChildIndex <= lastIndex)
{
///compare value at rChildIndex and at lChildIndex
///return the index where the value is smaller
if (x[rChildIndex].priority > x[lChildIndex].priority)
{
return rChildIndex;
}
else
{
return lChildIndex;
}
}
///case only left child exist
else if (lChildIndex <= lastIndex)
{
return lChildIndex;
}
///case both children missing
else
{
return -1;
}
}
public:
pque() {lastIndex=-1;}
void penque (int p, string n)
{
lastIndex++;
x[lastIndex].priority = p;
x[lastIndex].name = n;
maxreheapifyUpward(x,lastIndex);
}
RecType pdeque ()
{
RecType returnValue = x[0];
x[0] = x[lastIndex];
lastIndex--;
maxreheapifyDownward(x,lastIndex);
return returnValue;
}
bool isEmpty ()
{
if (lastIndex < 0){return true;}
else{return false;}
}
};
int main()
{
pque recordList;
while (recordList.userInput.priority >= 0)
{
cout << "input number" << endl;
cin >> recordList.userInput.priority;
if (recordList.userInput.priority == -1)
{
break;
}
cout << "input name" << endl;
cin >> recordList.userInput.name;
recordList.penque(recordList.userInput.priority, recordList.userInput.name);
}
while (!recordList.isEmpty())
{
recordList.userInput = recordList.pdeque();
cout << recordList.userInput.priority << " " << recordList.userInput.name << endl;
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.