Hi, I need help with my C++ program.

DESCRIPTIONS

The clients are arriving to get passports. The arriving clients register at the window. Each arriving client has a priority number and name. The priority numbers vary from 1 to 10. Ten being the highest priority and 1 being the lowest. At 10:00 am, the passport office will start serving clients that had registered by then at the window. The clients will be served not in the order that they arrived but in the order of their priority. First, all with priority 10; then those with priority 9 and so on.

To simulate the above, create an array based priority queue using max heap. Input registering clients one by one and enque them one by one into the priority queue. Each client input data will consist of client priority and name. Priority of -1 will indicate end of data. After all the clients are enqued, deque them from the priority queue one by one and display them one by one till priority queue becomes empty. See the test input data and the expected output below.

Code that needs to be fixed:

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

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;

}

Test data:

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