-heap: int* -length: int -capacity: int -reheapup (top: int, bottom: int): void
ID: 3868082 • Letter: #
Question
-heap: int*
-length: int
-capacity: int
-reheapup (top: int, bottom: int): void
-reheapdown (top: int, bottom: int): void
+PQueue (c: int):
~PQueue():
+enqueue (i: int): int
+dequeue (i: int&): int
+clear(): void
+isFull(): bool
+isEmpty(): bool
Use the above UML diagram to write a class implementing a priority queue implemented as a heap.
The class has the following attributes:
heap - a pointer that holds the memory address for a dynamically allocated array of integers used to store the heap.
length - the current "length" of the queue. Also serves to indicate the bottom of the heap. Could have named this attribute "bottom".
capacity - the number of elements of the dynamically allocated array.
The class has the following private methods:
reheapup - used to restore the heap after a value has been queued.
reheapdown - used to restore the heap after a value has been dequeued.
The class has the following public methods:
constructor - accepts an integer argument and initializes the class.
destructor - takes care of the dynamically allocated array
enqueue - adds it's argument to the heap. Returns 0 if successful, -1 otherwise.
dequeue - retrieves the highest value from the top of the heap through the reference parameter. Returns 0 if successful, -1 otherwise.
clear - resets the length to 0
isFull - returns true if the queue is full, false otherwise
isEmpty - returns true if the queue is empty, false otherwise.
PLEASE NOTE: FOLLOW AND USE THE ABOVE UML DIAGRAM (That includes function names as well) !! The class along with its function prototypes and its definitions should all be contained INSIDE THE HEADER FILE !!
PQueue-heap: int*
-length: int
-capacity: int
-reheapup (top: int, bottom: int): void
-reheapdown (top: int, bottom: int): void
+PQueue (c: int):
~PQueue():
+enqueue (i: int): int
+dequeue (i: int&): int
+clear(): void
+isFull(): bool
+isEmpty(): bool
Explanation / Answer
#include <iostream>
using namespace std;
//please read the comment for using extra print function for testing
class PQueue {
private:
int* heap;
int length;
int capacity;
void reheapup(int top, int bottom);
void reheapdown(int top, int bottom);
public:
PQueue(int c);
~PQueue();
int enqueue(int i);
int dequeue(int &i);
void clear();
bool isFull();
bool isEmpty();
//void print(); //please uncomment this code if you want to use print in main and also uncomment it body/definition
//below
};
//below all code implementation of function of heap is based on standard algorithem of heap
//which you can find it in any algorithm book
void PQueue::reheapup(int top, int down) {
int i = down;
int parent = i / 2;
if (i != top && heap[i] > heap[parent])
{
int temp = heap[i];
heap[i] = heap[parent];
heap[parent] = temp;
reheapup(top, parent);
}
}
void PQueue::reheapdown(int top, int down) {
int i = top;
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < down && heap[left] > heap[largest])
largest = left;
if (right < down && heap[right] > heap[largest])
largest = right;
if (largest != i)
{
int temp = heap[i];
heap[i] = heap[largest];
heap[largest] = temp;
reheapdown(largest, down);
}
}
PQueue::PQueue(int c) {
capacity = c;
heap = new int[capacity];
length = 0;
}
PQueue::~PQueue() {
delete[] heap;
}
int PQueue::enqueue(int i) {
if (isFull()) {
return -1;
}
else {
heap[length] = i;
reheapup(0, length);
++length;
return 0;
}
}
int PQueue::dequeue(int& i) {
if (isEmpty()) {
return -1;
}
else {
i = heap[0];
int temp = heap[0];
heap[0] = heap[length - 1];
heap[length - 1] = temp;
--length;
reheapdown(0, length - 1);
return 0;
}
}
void PQueue::clear() {
length = 0;
}
bool PQueue::isFull() {
return length == capacity;
}
bool PQueue::isEmpty() {
return length == 0;
}
//you should uncomment below function if you want to see the output of your code
/*
void PQueue::print() {
if (!isEmpty()) {
for (int i = 0; i < length; ++i) {
cout << heap[i] << " ";
}
cout << endl;
}
}
*/
//i used below code to test the correctness of our class and this is not part of solution
//only above code is part of solution
//if you want to test uncomment main function and test according to your need
//but before using the member function of your class I suggest you to see the definition of each member
//if you do not see them then there is high possibility that you get lot of error
//since you only want the header file
//please save the above code as nameYouWant.h file but PQueue.h would be more logical
//and if you use it as header then don't forget to use header gaurd
/*
int main() {
PQueue pq(10);
for (int i = 0; i < 10; ++i) {
pq.enqueue(i);
}
pq.print();
int k;
pq.dequeue(k);
cout << k << endl;
pq.print();
if (pq.isEmpty()) {
cout << "Prority queue is empty ! ";
}
else {
cout << "Prority queue is not empty ! ";
}
return 0;
}
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.