Hi, I just want to check if my C++ code follows the directions as it is stated i
ID: 3707295 • Letter: H
Question
Hi, I just want to check if my C++ code follows the directions as it is stated in the requeriments since the lab assigment is complicated to understand.
Priority Queue Using Heap
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:
#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;
return 0;
}
Txt File:
3 Jim
2 Judy
7 Jill
1 Jimmy
10 Joe
4 Jacob
8 Joseph
9 Josephine
5 Jackie
6 John
-1
Explanation / Answer
YES , I checked the assignment
Points to be Noted:
1) You have created Array based Queue which is expected in the requirement.
2) MAX Heap as well
3) Correct Output
It looks fine to me. Only thing left is Add Comments in your code
Ask me if there is any doubts/concern.Comment and I will respond for any queries/doubts.
PLEASE UPVOTE if its helpful
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.