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

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>

quit

Exit the program

heapsort> quit

Error Handling

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
Academic Honesty!
It is not our intention to break the school's academic policy. Projects posted are only used as a reference and should not be submitted as is. We are not held liable for any misuse of the solutions. Please see the frequently asked questions page for further questions and inquiries.
Kindly fill out the form. Please provide a valid email address and we'll get back to you in less than 24 hours. We will be sending an invoice through PayPal upon confirmation. We are a non profit organization however we need an amount to keep this organization running, and to be able to complete our research and development.