Given an array A and a minimum heap H which of the following are true?

Question

I got this series of questions, each needs to either be proved or disproved (w/ example).

1. If $A$ is sorted in non-descending order, it is a valid minimum heap.
2. If $H$ is represented by $A$, therefore $A$ is a sorted array in non-descending order.
3. If $H$ is represented by $A$ (such that $A[1]$ is the first element), then for any $2i < j$, the expression $A[i] < A[j]$ is true
4. If $H$ is represented by $A$ (such that $A[1]$ is the first element), then the following is a sorted array:
5. If we sort each level in H separately, it will still be a valid minimum heap.

This was my proof:

1. true. Tested for with arrays $[1]$, $[1,2]$, $[1,2,2]$ that it works. Assume it works for any size array $k < n$. Then set the array size to $k=n-1$. Added an element to the list. Since the list is already sorted, the new element can either be equal to the last or larger than the largest element in the list. So it will always be a leaf. Maintaining minimum heap.
2. false. $[10,50,40]$ is a valid minimum heap.
3. ?. Apparently the answer is false but any heap I tested worked.. So I don't understand how this could be false.
4. ?. I didn't really understand the order of operations here and could not find the series. Is it $2*log(n)-1$ or $2*log(n-1)$ or $2*(log(n)-1)$ or ...? In any case, I couldn't make sense of it.
5. true. Same as (1) essentially. Assume for one level, two levels. Check for n levels.

How did I do? Also, help with 3-4 would be much appreciated!

Answer 1

I think you are right in 1,2,5. I didnt really understand your proof for 5, since it should be different from 1.

Also, the proof for 1 can be greatly simplified: $A[i]\le A[2i],A[2i+1]$ is the definition of the minimality property in the heap, and you can directly show that using the fact your list is ordered.

About 3, try to create a big heap such that the left subheap has large values but the right subheap has small values

About 4, it doesn't really matter if its $2\log(n) -1$ or $2(\log(n)-1)$. Think of the series as a path from the root to some leaf. It should help you figure that out :)

I hope i managed to help you!