if a question contains a piece of code provided as a hint, the code may not work. Thus, it is your responsibility to make sure that you fix the code appropriately if you choose to use it. For all questions, unless stated in the question, input data may be generated randomly or read from the keyboard. Make sure you read the Syllabus for the policy on code submissions.

IMPORTANT: for all dynamically allocated data structures, a DESTRUCTOR must be implemented that deallocates all memory used by the data structure.

IMPORTANT: any MakeEmpty method implemented in a dynamically allocated data structure MUST DEALLOCATE all memory used by the data structure.

IMPORTANT: any data structure must be implemented to work with any number of elements. For static data structures, the data structure should work if the size of the array is changed in the source code.

IMPORTANT: for each dynamically allocated data structure with pointers, you must implement a class for the node data (and operations) and a separate class that implements the data structure operations. You may implement additional classes if you wish.

IMPORTANT: any observer must be declared const and any class attribute or method that is not to be used by a client must be private.

Implement the heapsort method to sort (ascending) an array of integers.

Your code must with the following implementation of main:

int main()

{

int Items[] = {12,34,6,78,91,22,52,99};

cout<<" Unsorted elements: ";

for (int i=0;i

cout<<" "<

cout<

HeapSort(Items,sizeof(Items)/sizeof(int));

cout<<" Sorted elements: ";

for (int i=0;i

cout<<" "<

cout<

return 0;

}

Your code must produce the following output:

Unsorted elements: 12 34 6 78 91 22 52 99

Sorted elements: 6 12 22 34 52 78 91 99

IMPORTANT: you MUST USE ONLY ONE ARRAY in your implementation.

IMPORTANT: you MUST SORT ASCENDING!