Question
The goal of this assignment is to reinforce the concept of heap and implement priority queue as a heap in C++. For this assignment, use
The goal of this assignment is to reinforce the concept of heap and implement priority queue as a heap in C++. For this assignment, use the zip file Priority_Queue_Heap.zip provided with this assignment. It includes five files. Compile, and run the files and understand how class heap and the main function work. Complete the implementation of the template class PQ_Heap.template. The only member data we need for this class is a heap object. To implement all priority queue functions defined in file PQ_Heap.h, you may need to include additional functions to files heap.h and heap.template (provided in the zip file). Do NOT rename these 2 files. Next, in a new test file testPQH.cpp, test the class PQ_Heap. Use a menu system as follows. The menu allows the user to start with option 0 (to select and set the type of queue), then exercise other options. 0. Enter Queue Type (int or string) 1. Enqueue Element 2. Dequeue Element 3. Check is_Full 4. Check is_Empty 5. Print Size 6. Display Front Element 7. Print Queue Elements 8. Quit program For option 7, utilize function check_heap(). Make sure the code gives proper messages for special cases, such as dequeue from an empty queue or enqueue to a full queue, etc. Re-display the menu after each option is fully exercised
#ifndef HEAP_H
#define HEAP_H
// This class implements a heap as described in the text.
template
class heap {
public:
static const int CAPACITY = 50;
heap() {
size = 0;
}
bool is_empty() const { return size == 0;}
bool is_full() const { return size == CAPACITY; }
/**
* Remove the largest value from this heap and return it.
*
* Precondition: heap is not empty.
*/
T remove();
/**
* Inserts the 'value' into the heap.
*
* Precondition: heap is not full
*/
void insert(const T& value);
/**
* Check if the heap is valid.
* Prints out each parent and its children (for all nodes with children)
* Stops when a parent is less than one or both of its children
* Prints 'check' for each parent that is greater than or equal to its children
*/
bool check_heap();
private:
T data[CAPACITY];
int size;
};
#include "heap.template"
#endif // HEAP_H
===========================================================================
#include
#include
#include
#include
/*
*parent index is p, children are at indices 2*p+1 and 2*p+2
*You must check that those are in range
*
*child index is c, parent index is (c-1)/2 (integer division)
*/
/**
* Inserts the 'value' into the heap.
*
* Precondition: heap is not full
*/
template
void heap
assert(!is_full());
// add the value to a new node in proper position
data[size] = value;
size++;
// move the value up the tree as needed
int child = size-1; // index of the new 'node'
int parent = (child-1)/2; // index of the parent
while((child > 0) && (data[parent]
// swap parent and child values
T tmp = data[parent];
data[parent] = data[child];
data[child] = tmp;
// update parent and child
child = parent; // this is where new value is!
parent = (child-1)/2;
}
}
/**
* Remove the largest value from this heap and return it.
*
* Precondition: heap is not empty.
*/
template
T heap
assert(!is_empty());
// grab first element, save it for return later
T save = data[0];
// copy last value in list to the beginning
// decrement size
data[0] = data[size-1];
size--;
// shift the new first element down until it finds its place
int parent = 0;
int left_child = 2*parent+1;
int right_child = 2*parent+2;
bool still_working = true;
while(still_working && left_child
if(right_child >= size) {
// only the left child to worry about
if(data[parent]
// out of order, so swap them
T t = data[parent];
data[parent] = data[left_child];
data[left_child] = t;
parent = left_child;
still_working = false; // we must be done!
} else {
still_working = false;
}
} else {
// two children
if(data[left_child] > data[right_child]) {
//left child larger
if(data[parent]
// out of order, so swap them
T t = data[parent];
data[parent] = data[left_child];
data[left_child] = t;
parent = left_child;
} else {
still_working = false;
}
} else {
// right child larger
if(data[parent]
// out of order, so swap them
T t = data[parent];
data[parent] = data[right_child];
data[right_child] = t;
parent = right_child;
} else {
still_working = false;
}
}
left_child = 2*parent + 1;
right_child = 2*parent + 2;
}
}
return save;
}
/**
* Check if the heap is valid.
* Prints out each parent and its children (for all nodes with children)
* Stops when a parent is less than one or both of its children
*/
template
bool heap
for(int p = 0; p
int cl = 2*p+1;
int cr = 2*p+2;
std::cout
if(cl
std::cout
if(data[p]
std::exit(1);
}
}
if(cr
std::cout
if(data[p]
std::exit(1);
}
std::cout
}
return true;
}
=====================================================================================
/**
* Insert a few elements into a heap and the remove them
* one by one and see if we get them in the right.
*/
#include "heap.h"
#include
#include
#include
#include
using namespace std;
void inTest() {
cout
heap
hp.insert(11);
hp.insert(22);
hp.insert(33);
hp.insert(44);
hp.insert(55);
cout
hp.check_heap(); //check if heap is correct
cout
int x = hp.remove();
cout
x = hp.remove();
cout
x = hp.remove();
cout
x = hp.remove();
cout
x = hp.remove();
cout
cout
cout
cout
}
void charTest() {
cout
heap
char ch;
for(int i = 0; i
cout
cin >> ch;
hp2.insert(ch);
}
cout
hp2.check_heap(); //check if heap is correct
cout
cout
while(!hp2.is_empty()) {
char ch = hp2.remove();
cout
}
}
int main() {
inTest();
charTest();
}
======================================================================================
#ifndef PRIORITY_QUEUE_HEAP_H
#define PRIORITY_QUEUE_HEAP_H
template
class priority_queue_heap {
priority_queue_heap();
// Return true if priority queue is empty; otherwise return false
bool is_empty() const;
// Return true if priority queue is full; otherwise return false
bool is_full() const;
// Return (don't remove) the front element from the priority queue
// Precondition: priority queue is not empty.
T front();
// return number of elements in the queue
int size();
// Remove the largest value from this priority queue and return it.
// Precondition: priority queue is not empty.
T dequeue();
// Inserts the 'value' into the priority queue.
// Precondition: priority queue is not full
void enqueue(const T& value);
};
#include "PQ_Heap.template"
#endif // PRIORITY_QUEUE_HEAP_H
=============================================================================================
*** Make another template file called PQ_Heap.temp
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Business Law Text and Cases
Authors: Kenneth W. Clarkson, Roger Miller, Frank B. Cross
14th edition
978-1305967250, 1305967259, 978-1337514422, 133751442X, 978-1337374491
