Design and implement a heap sort program to display the max heap, remove the highest node and add a new node. The program should have at least a header file and a main driver file.

Removing the root in a heap – after the root is removed, the tree must be rebuilt to maintain the heap property:
Move the last node to replace the root;
Let the root be the current node;
While ( the current node has children and the current node is smaller than one of its children)
{ Swap the current node with the larger of its children;
The current node now is one level down; }

Adding a new node – to add a new node to the heap, first add it to the end of the heap and then rebuild the tree as follows:
Let the last node be the current node;
While (the current node is greater than its parent)
{ Swap the current node with its parent;
The current node now is one level up;}

Sample output:

Enter the positive integers to put in heap, enter -9 to stop.

7 5 16 85 95 4 11 65 43 10 13 9 -9

The Heap is:

95 85 11 65 16 9 7 5 43 10 13 4

Display the Max-heap
Add an Item
Remove the Largest Item
Exit
Enter choice: 3

Remove Item: 95

Display the Max-heap
Add an Item
Remove the Largest Item
Exit
Enter choice: 3

Remove Item: 85

Display the Max-heap
Add an Item
Remove the Largest Item
Exit
Enter choice: 3

Remove Item: 65

Display the Max-heap
Add an Item
Remove the Largest Item
Exit
Enter choice: 1

The Heap is: 43 16 11 13 10 9 7 5 4

Display the Max-heap
Add an Item
Remove the Largest Item
Exit
Enter choice: 2

Add Item: 14

Display the Max-heap
Add an Item
Remove the Largest Item
Exit
Enter choice: 1

The Heap is: 43 16 11 13 14 9 7 5 4 10

Display the Max-heap
Add an Item
Remove the Largest Item
Exit