====================================================================================================
Q: Which sorting algorithm?

A: Any sorting algorithm of your choice. You may even use stl/stdlib sorting function.
====================================================================================================
Q: Is sorting necessary?

A: No. Since only one key is out of order, swapping the minimum of parent with the maximum of child serves the purpose.
====================================================================================================
Q: What is the difference between n and nmax?

A: nmax is a maximum bound for n that the user is supposed to supply. This is needed for allocating sufficient memory to the node array. You may take nmax = 1024.
====================================================================================================
Q: Can we change the prototype of the calls?

A: If you want to add extra parameters, go ahead. But your passing of H is by value. So if the function modifies H, you should return H, like:

H = insert(H,x);
====================================================================================================
Q: Do I need to write heapify?

A: heapify is needed only in delmax. So you can embed heapify in delmax itself. Having a separate function is not bad anyway. Just call it from delmax.
====================================================================================================
Q: Instead of multiple arrays in different nodes, can we use a single large array with logical partitioning?

A: You can do many such things. But follow the instructions of the assignment statement.
====================================================================================================
Q: What is i in heapify?

A: heapify needs an index. i is that index. You do heapify only at the root (in delmax), so i is 0 or 1 depending on what kind of indexing you follow.
====================================================================================================
Q: Not getting the same output as in the given samples.

A: Just check that your heap obeys the heap ordering property. If yes, there is no need to match with the samples. Heaps are not unique anyway.
====================================================================================================
Q: Do I need to print the node keys in sorted order?

A: No need. For example, look at the last line in the sample output.
====================================================================================================