# c code using max heap

AcademicWritersDen.com boasts a team of highly skilled and experienced writers who specialize in various academic fields. The company carefully selects its writers through a rigorous screening process to ensure that they possess the necessary qualifications and expertise. Whether it’s an essay, research paper, or any other homework assignment, students can rely on AcademicWritersDen.com to connect them with professionals who have an in-depth understanding of the subject matter. This ensures that the work delivered is of high quality and meets the academic standards set by educational institutions.

__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.

__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

__DEFINITIONS__

__Max Heap__

Max Heap is a heap in which the parent is always smaller than all of its children.

__Min Heap__

Min Heap is a heap in which the parent is always smaller than all of its children

__Array Based Max Heap__

Array Based Max Heap is a max heap which is implemented using an array.

__Array Based Min Heap__

Array Based Min Heap is a min heap which is implemented using an array.

__Max Heap Priority Queue__

Max Heap Priority Queue is a priority queue which is a max heap before an enqueue or a dequeue operation is started. In carrying out any of these operations, its max heap property may be temporarily disturbed. However, at the completion of each of these operation, the priority queue must be a max heap again.

__Min Heap Priority Queue__

Min Heap Priority Queue is a priority queue which is a min heap before an enqueue or a dequeue operation is started. In carrying out any of these operations, its min heap property may be temporarily disturbed. However, at the completion of each of these operation, the priority queue must be a min heap again.

__IMPLEMENTATION__

Implement the priority queue class using max heap array. The priority queue class would have functions: penque (the priority enque), pdeque (priority deque) and isEmpty. These functions are described below:

__penqueue__

This method will be used to enqueue an item to the priority queue. This method will receive a customer record

as a parameter and queue it to the priority queue. The priority queue will be a miax heap before the method is called. During the operation, its max heap property may be temporarily disturbed. However, when the method returns, the queue will be a max heap again.

__pdequeue__

Pre-condition: This method will be called only when the que is NOT empty.

This method will be used to deque an item from the priority queue. This method will receive no parameter, It will deque an item from the priority queue and return it to the caller. The queue will be a max heap before the method is called. During the operation, the queue’s max heap property may be temporarily disturbed. However, when the method returns, the queue will be a max heap again.

isEmpty

This method will return true or 1 if the queue is empty. Otherwise, it will return false or 0. This method can be called to ensure that the queue is not empty before calling the dequeue method above.

__ALGORITHM__

__penqueue__

(The heap array is a max heap).

Increase the length of the heap array by 1.

Store the item to be enqueued to the newly added last element of the heap array.

(The heap array is a max heap except that the newly added last element may have disturbed the max heap property).

Call maxreheapifyUpward to maxreheapify the heap array.

(The heap array is a max heap again).

__pdequeue__

(The heap array is a max heap).

Save the contents of the first element of the heap array.

(This element will be returned at the end of the method).

Copy the contents of the last element of the array in the first element of the array.

Decrease the length of the heap array by 1.

(The heap array is a max heap except that the newly copied first element may have disturbed the max heap).

Call maxreheapifyDownward to maxreheapify the heap array.

(The heap array is a max heap again).

Return the earlier saved first element of the heap array.

__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;

}