Exercise 2: Build Heap Time

Your textbook proves that the Build-Max-Heap algorithm is O(n). You will perform an empirical experiment to support that its running time does increase linearly with the size (n) of the array placed in max-heap order.

Start with the following program: CSI318-Exercise 2 (Build Max Heap).zip Download CSI318-Exercise 2 (Build Max Heap).zip, which contains C++ code to time runs of a buildMaxHeap() function on randomized arrays of increasing size.

To complete the empirical experiment, do the following:

1. Implement the Build-Max-Heap algorithm from the book in the empty function buildMaxHeap(). You should also write other functions, such as one to recursively implement the Max-Heapify procedure. Note: The array is made large enough so that you can ignore element [0] and use 1-based indices like the book. Document your implementation with comments. Include your name at the top of the program.
2. Run the program, which uses functionality from the <chrono> library to time multiple runs at each array size.
3. Collect the output from the program as a text file.
4. Use Excel (or Google Sheets) to plot the array sizes (n) vs. accumulated times across multiple runs (microseconds). Add a descriptive title to the top of the chart, label the x and y axes, and add a trendline. Your plot should (hopefully) show a linear trend! Export the plot as an image.

Zip up the folder containing the completed Visual Studio solution (remember to remove some files per the instruction video). Upload the zipped folder, a separate text file (program output), and image (plot) here for this assignment.