Implement a maxheap for integers using the array representation for heaps. You will need to create a class for the heap. This class will at least contain the internal structure of the heap (array), as well as functions for insertion and eletion of the maximum element. Recall that a heap stores its elements in the array starting at index 1, not 0. You are not allowed to use the C++ standard template library.
Once the program is started, it will print out the promt "heapsort> " (> is followed by a whitespace):
./a.out
heapsort>
You will implement the commands "sort" and "quit":
Sort takes multimple integers as arguments. The first number represents the number of elements that will follow, i.e. the first number is not part of the numbers to be sorted. Sort the input by inserting them in the order read into the heap. Then repeatedly execute your implementation of "deletemax" to sort the elements. Make sure to restore the heap condition after every insertion or deletion. Print the contents of the heap array (starting at index 1) before each execution of deletemax. The output will be on a single line. The contents of the array are separated by commas and enclosed in parenthesis. Then repeat the prompt.
Note on the "bubble-down" operation to restore the heap property after executing deletemax: If both children have the same value, choose the left child to exchange with.
heapsort> sort 1 4
(4)
heapsort> sort 2 6 4
(6,4)(4)
heapsort> sort 3 2 8 43
(43,2,8)(8,2)(2)
heapsort>
Exit the program
heapsort> quit
If the command received from the user input is not supported, print out an error message starting with "Error!". (Do not capitalize the entire word "Error") You can assume that the user only tries to insert numbers.
Example of program execution:
g++ *.cpp
./a.out
heapsort> sort 1 4
(4)
heapsort> sort 2 6 4
(6,4)(4)
heapsort> sort 3 2 8 43
(43,2,8)(8,2)(2)
heapsort> sort 5 4 7 2 3 8
(8,7,2,3,4)(7,4,2,3)(4,3,2)(3,2)(2)
heapsort> hi
Error! Command not supported.
heapsort> quit