The goal of this assignment is to reinforce the Heap data structure in C++.

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 demonstrate two implementations of priority queues.

- priority_queue_simple

- priority_queue_heap

//Priority_Queue_Heap Header File

#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

#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

//Template File

#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 < size; i++ ) { if(data[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 < CAPACITY); size++; data[size-1] = value; }

//Main File

#include "heap.h" #include #include using namespace std;

int test1() { heap hp; hp.insert(1); hp.insert(2); hp.insert(3); hp.insert(4); hp.insert(5); hp.check_heap();

int x = hp.remove(); cout << "removed " << x << endl; x = hp.remove(); cout << "removed " << x << endl; x = hp.remove(); cout << "removed " << x << endl; x = hp.remove(); cout << "removed " << x << endl; x = hp.remove(); cout << "removed " << x << endl;

cout << "empty? " << hp.is_empty() << endl; }

void test2() { srand(time(NULL)); heap hp; for(int i = 0; i < 30; i++ ) { hp.insert(rand()); } while(!hp.is_empty()) { int x = hp.remove(); cout << x << endl; }

}

int main() { test1(); test2():

}