Requirements 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

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 << size << std::endl;

// 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] < data[child])) {

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

}

// 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) { // while the parent has at least one child

if(right_child >= size) {

// only the left child to worry about

if(data[parent] < data[left_child]) {

// 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] < data[left_child]) {

// 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] < data[right_child]) {

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

* Prints 'check' for each parent that is greater than or equal to its children

*/

template

bool heap::check_heap()

{

for(int p = 0; p < size; p++ ) {

int cl = 2*p+1;

int cr = 2*p+2;

std::cout << std::setw(5) << p << std::setw(10) << data[p];

if(cl < size) { // p has a left child?

std::cout << std::setw(10) << data[cl];

if(data[p] < data[cl]) {

std:

exit(1);

}

}

if(cr < size) { // p has a right child?

std::cout << std::setw(10) << data[cr];

if(data[p] < data[cr])

std::exit(1);

}

std::cout << std::endl;

}

return true;

}

Main.cpp

/**

* 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

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();

}

Priority_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

#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 < 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;

}

priority_queue_heap.template

????????????