Complete using the given code. Please complete ALL the class definitions in maxheap.cpp

Implement a MaxHeap and HeapSort. We are providing some sample code and input files:

demo.cpp <- main method to try your implementation

inputs <- folder with several sample inputs

maxheap.cpp <- the actual implementation )only file you have to modify)

maxheap.hpp <- header file

The code provided follows closely the implementation in the textbook.

To compile, run $ g++ -o heapsort demo.cpp maxheap.cpp To test your implementation with a sample input file, run $ ./heapsort inputs/input.10.1 This will test a few methods (you need to check the maxheap after each step manually), and run heapsort (the code will check whether the output is sorted automatically). To test your implementation with all sample files with one command, time for f in inputs/input.10*; do echo $f; ./heapsort $f; done The command time will let you know how long it took to run the code. You may want to store the output in a file so that you can look at it carefully: time for f in inputs/input.10*; do echo $f; ./heapsort $f; done > output

maxheap.hpp:

#include using namespace std;

class MaxHeap { private: vector arr; int left(int parent); int right(int parent); int parent(int child); void percolateDown(int index); // used for giving the heap max heap structure void percolateUp(int index); // used for inserting in the heap at proper position void heapify(); void buildHeap(vector A,int n); public: MaxHeap(); ~MaxHeap(); void insert(int element); int deleteMax(); void display(); void heapsort(vector& A,int n); int size(); };

maxheap.cpp

#include "maxheap.hpp" #include #include

MaxHeap::MaxHeap() {} MaxHeap::~MaxHeap() {}

/* ALL YOUR CODE GOES HERE The methods below either - don't do anything at all, or - return 0 just so that the code compiles

You have to implement every method in this class */

int MaxHeap::size() { return 0; }

int MaxHeap::left(int parent) { return 0; }

int MaxHeap::right(int parent) { return 0; }

int MaxHeap::parent(int child) { return 0; }

void MaxHeap::insert(int element) { }

int MaxHeap::deleteMax() { return 0; }

void MaxHeap::display() { vector::iterator it; cout << "MaxHeap:- "; for(it=arr.begin(); it!=arr.end(); ++it) { cout << *it << " "; } cout << endl; }

void MaxHeap::percolateUp(int index) {

}

void MaxHeap::percolateDown(int index) {

}

void MaxHeap::heapify(){

}

void MaxHeap::buildHeap(vector A,int n) {

}

void MaxHeap::heapsort(vector& A,int n) {

}

demo.cpp

#include "maxheap.hpp"

#include

#include

int main(int argc, char*argv[]) {

//demo functions of the maxheap class

MaxHeap* myheap = new MaxHeap();

cout << "========================================" << endl;

cout << "Trying some methods from the MaxHeap class ...." << endl;

cout << "You must check that the output is correct manually (or write code that does it automatically)" << endl ;

cout << "========================================" << endl;

myheap->insert(700);

cout << "insert 700" << endl;

myheap->display();

myheap->insert(500);

cout << "insert 500" << endl;

myheap->display();

myheap->insert(100);

cout << "insert 100" << endl;

myheap->display();

myheap->insert(800);

cout << "insert 800" << endl;

myheap->display();

myheap->insert(200);

cout << "insert 200" << endl;

myheap->display();

myheap->insert(400);

cout << "insert 400" << endl;

myheap->display();

myheap->insert(900);

cout << "insert 900" << endl;

myheap->display();

int heapSize = myheap->size();

for ( int i = 0; i < heapSize/2; i++ ) {

cout << "Get and delete max element: " << myheap->deleteMax() << endl;

myheap->display();

}

cout << "========================================" << endl;

delete myheap;

//heapsorting numbers in a file

vector A;

if(argc!=2) {

cout<<"Provide an input file as argument";

} else {

FILE *file = fopen(argv[1], "r");

if(file == 0){

cout << "ERROR: file does not exist" << endl;

return -1;

}

else {

int x;

fscanf(file, "%d", &x);

while(!feof(file)) {

A.push_back(x);

fscanf(file, "%d", &x);

}

fclose(file);

}

}

int n = A.size();

cout << endl << endl;

cout << "========================================" << endl;

cout << "Checking if HeapSort works ..." << endl;

cout << "Input size: " << n << endl;

cout << "========================================" << endl;

if (n <= 10) {

cout << "This it the input:" << endl;

for(int i=0; i

cout << A[i] << " ";

}

cout << endl;

}

else{

cout << "Input is too large to display" << endl;

}

MaxHeap *myheap2 = new MaxHeap();

myheap2->heapsort(A,n);

if (n <= 10) {

cout << "And this is the sorted output:" << endl;

for(int i=0; i

cout << A[i] << " ";

}

cout << endl;

}

else {

cout << "Sorted output is too large to display" << endl;

}

cout << "Checking if the output is actually sorted ..." << endl;

bool sorted = true;

for (int i=1; i

if (A[i-1] > A[i]){

cout << "Output is NOT SORTED: " << A[i-1] << " is greater than " <<

A[i] << "(index " << i << ")" << endl;

sorted = false;

}

}

if (sorted) {

cout << "\tThe output is sorted" << endl;

}

cout << "========================================" << endl << endl << endl << endl;

delete myheap2;

return 0;

}