Project 3CS 271: Data Structures Fall 2019Instructor: Ashwin Lall Due: 2019-09-30Part 1: Heap QuestionsAnswer the following questions in a PDF typeset in LATEX:1. Where in a min-heap might the largest element reside, assuming that all elements aredistinct?2. Is an array in sorted order a min-heap? Why or why not?3. Is a min-heap always a sorted array? Why or why not?Part 2: Heap and Heapsort ImplementationImplement a MinHeap template class, and the heap sort algorithm. The heap sort methodshould return a copy of the array in ascending sorted order. The class definition follows.template class MinHeap{public:MinHeap(int n = DEFAULT_SIZE); // default constructorMinHeap(KeyType initA[], int n); // construct heap from arrayMinHeap(const MinHeap& heap); // copy constructor~MinHeap(); // destructorvoid heapSort(KeyType sorted[]); // heapsort, return result in sortedstd::string toString() const; // return string representationMinHeap& operator=(const MinHeap& heap); // assignment operatorprivate:KeyType *A; // array containing the heapint heapSize; // size of the heapint capacity; // size of Avoid heapify(int index); // heapify subheap rooted at indexvoid buildHeap(); // build heapint leftChild(int index) { return 2 * index + 1; } // return index of left childint rightChild(int index) { return 2 * index + 2; } // return index of right childint parent(int index) { return (index – 1) / 2; } // return index of parentvoid swap(int index1, int index2); // swap elements in A1void copy(const MinHeap& heap); // copy heap to this heapvoid destroy(); // deallocate heap};Notes:• The second constructor should dynamically allocate A, copy the contents of initA toA, and then call buildHeap. (Therefore, heapSort need not call buildHeap.)• The heapSort method should return the sorted array in ascending order in the pa-rameter named sorted. It is the responsibility of the caller to allocate sorted to belarge enough to hold the result. So here is how one could sort an array of integersusing heap sort:int *A = new int[length];// populate A with integers hereMinHeap heap(A, length);heap.heapSort(A);// print A here• Your toString function should return a string of the underlying array in the sameformat as Project 0.• Include suitable preconditions and postconditions in the comments before eachmethod.• Include unit tests (using assert and the toString method) for each of your methods.Plot the running time of heap sort for a sequence of sufficiently large input sizes andcompare this to the running times of insertion sort and merge sort (and perhaps otheralgorithms that you implemented in CS 173) and add this plot to your LATEXfile. The codebelow illustrates how you can time one run of a sorting algorithm.#include int main(){# set up stuff heretimeval timeBefore, timeAfter;long diffSeconds, diffUSeconds;gettimeofday(&timeBefore, NULL);# call sort heregettimeofday(&timeAfter, NULL);2diffSeconds = timeAfter.tv_sec – timeBefore.tv_sec;diffUSeconds = timeAfter.tv_usec – timeBefore.tv_usec;cout << diffSeconds + diffUSeconds/1000000.0 << " seconds" << endl;return 0;}You should acquire times for at least 100 values of n to get plots that are “smooth”enough to empirically see the running times of the algorithms.Submitting your workPlease upload to NoteBowl the following files:• Your PDF file made in LATEX• heap.cpp• test heap.cpp• timesort.cpp• Makefile — this should compile your unit tests into an executable called test heapand your sort program into an executable called timesort.Please make sure that your code compiles and runs on the Linux machines in Olin 219.3
