Please create a priority_queue_heap.template file and use c++. The files needed are below:

HEAP.H

#ifndef HEAP_H #define HEAP_H

/** * This class implements a heap as described in the text. * We will treat it as a priority queue. */

template class heap { public: static const int CAPACITY = 10;

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

HEAP.Template

#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::insert(const T& value) { assert(!is_full());

//std::cout

// 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]

// it's a heap!

}

/** * Remove the largest value from this heap and return it. * * Precondition: heap is not empty. */ template T heap::remove() { 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--;

// size--; // data[0] = data[size];

// sift 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 = size) { // only the left child to worry about if(data[parent] data[right_child]) { //left child larger if(data[parent]

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 * Prints 'check' for each parent that is greater than or equal to its children */ template bool heap::check_heap() { for(int p = 0; p

PRIORTITY-QUEUE_HEAP.h

#ifndef PRIORITY_QUEUE_HEAP_H #define PRIORITY_QUEUE_HEAP_H

template class priority_queue_heap { priority_queue_heap();

bool is_empty() const;

bool is_full() const;

/** * Remove the largest value from this priority queue and return it. * * Precondition: priority queue is not empty. */ T remove();

/** * Inserts the 'value' into the priority queue. * * Precondition: priority queue is not full */ void insert(const T& value);

};

#include "priority_queue_heap.template"

#endif // PRIORITY_QUEUE_HEAP_H

PRIORITY_QUEUE_SIMPLE.H

#ifndef PRIORITY_QUEUE_SIMPLE_H #define PRIORITY_QUEUE_SIMPLE_H

/** * This class implements a priority queue using a very simple strategy: * Store the values in an array. * Add new values at the end. * When asked to remove a value, search for the largest (linear search) * */

template class priority_queue_simple { public: static const int CAPACITY = 30;

priority_queue_simple() { size = 0; }

bool is_empty() const { return size == 0; }

bool is_full() const { return size == CAPACITY; }

/** * Remove the largest value from this priority queue and return it. * * Precondition: priority queue is not empty. */ T remove();

/** * Inserts the 'value' into the priority queue. * * Precondition: priority queue is not full */ void insert(const T& value);

private: T data[CAPACITY]; int size; };

#include "priority_queue_simple.template"

#endif // PRIORITY_QUEUE_SIMPLE_H

PRIORITY_QUEUE_SIMPLE.Template

#include

/** * Remove the largest value from this priority queue and return it. * * Precondition: priority queue is not empty. */ template T priority_queue_simple::remove() { assert(size > 0); int imax = 0; for(int i = 1; i data[imax]) imax = i; } T tmp = data[imax]; data[imax] = data[size-1]; size--; return tmp; }

/** * Inserts the 'value' into the priority queue. * * Precondition: priority queue is not full */ template void priority_queue_simple::insert(const T& value) { assert(size 2. Priority Queue Download the project Priority_Queue Heap. Finish the implementation of priority_ queue_heap. The only member data will be a heap. Modify the main.cpp to create two new functions to of priority queues. . priority_ queue_simple priority_queue heap 2. Priority Queue Download the project Priority_Queue Heap. Finish the implementation of priority_ queue_heap. The only member data will be a heap. Modify the main.cpp to create two new functions to of priority queues. . priority_ queue_simple priority_queue heap