I need to implement a heapsort in C++ using vector implementation, please fill in the heapsort function and buildHeap function (last 2 functions in the code). If one of the other functions look incorrect feel free to change those as well.

CODE:

#include "maxheap.hpp" #include #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 arr.size(); return 0; }

int MaxHeap::left(int parent) { return (2*parent + 1); return 0; }

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

int MaxHeap::parent(int child) { return (child - 1 )/ 2; return 0; }

void MaxHeap::insert(int element) { arr.push_back(element); // add new element to the end of vector

int index = size() - 1; percolateUp(index); }

int MaxHeap::deleteMax() { arr[0] = arr.back(); arr.pop_back(); percolateDown(0);

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) { if (index && arr[parent(index)] < arr[index]) { swap(arr[index], arr[parent(index)]); percolateUp(parent(index)); } }

void MaxHeap::percolateDown(int index) { int left_ind = left(index); int right_ind = right(index);

int largest = index;

if (left_ind < size() && arr[left_ind] > arr[index]) { largest = left_ind; } if (right_ind < size() && arr[right_ind] > arr[largest]) { largest = right_ind; } if (largest != index) { swap(arr[index], arr[largest]); percolateDown(largest); } }

void MaxHeap::heapify(int i) { int left_ind = left(i); int right_ind = right(i); int smallest = i;

if (left_ind < size() && arr[left_ind] < arr[i]) smallest = left_ind;

if (right_ind < size() && arr[right_ind] < arr[smallest]) smallest = right_ind;

if (smallest != i) { swap(arr[i], arr[smallest]); heapify(smallest); } } void MaxHeap::buildHeap(vector A,int n) { }

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

}