Hi, I need help with my C++ code using priority queue. I need to create an array
ID: 3708247 • 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.
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
public interface ListInterface {
public boolean isEmpty();
public int size();
public void add(int index, Object item)
throws ListIndexOutOfBoundsException, ListException;
public Object get(int index)
throws ListIndexOutOfBoundsException;
public void remove(int index)
throws ListIndexOutOfBoundsException;
public void removalAll();
} //end ListInterface
Modify the ListArrayBased class
Modify ListArrayBased by performing the following:
1) change the name of the class from ListArrayBased to ComparableListArrayBased
2) change ListInterface to ComparableListInterface
3) change Object to Comparable
4) add a method corresponding to the following UML:
+isInAscendingOrder() : boolean {query}
isInAscendingOrder returns true if the list is in ascending sorted order, else returns false
// *************************************************************
// Array-based implementation of the ADT list.
// *************************************************************
public class ListArrayBased implements ListInterface {
private static final int MAX_LIST = 50;
private Object items[]; // an array of list items
private int numItems; // number of itmes in list
public ListArrayBased() {
items = new Object[MAX_LIST];
numItmes = 0;
} // end default constructor
public boolean isEmpty() {
return (numItems ==0);
} // end isEmpty
public int size() {
return numItems;
} // end size
public void removeAll() {
// Creates a new array; marks old array for
// garbage collection.
items = new Object[MAX_LIST];
numItems = 0;
} // end removeAll
public void add (int index, Object item)
throws ListIndexOutOfBoundsException {
if (numItems >= MAX_LIST) {
throw new ListException("ListException on add");
} // end if
if (index >= 0 && index <= numItems) {
// make room for new element by shifting all items at
// positions >= index toward the end of the
// list (no shift if index == numItems+1)
for (int pos = numItems - 1; pos >= index; pos--) {
items[pos+1] = items[pos];
} // end for
// insert new items
items[index] = item;
numItems++;
}
else { // index out of range
throw new ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on add");
} // end if
} // end add
public Object get(int index)
throw ListIndexOutOfBoundsException {
if (index >= 0 && index < numItems) {
return items[index];
}
else { // index out of range
throw new ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on get");
} // end if
} // end get
public void remove(int index)
throw ListIndexOutOfBoundsException {
if (index >= 0 && index < numItems) {
// delete item by shifting all items at
// positions > index towards the beginning of the list
// (no shift if index == size)
for (int pos = index + 1; pos < numItems; post++) {
items[pos-1] = items[pos];
} // end for
numItems--;
}
else { // index out of range
throw new ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on remove");
} // end iff
} // end remove
} #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.