I got this series of questions, each needs to either be proved or disproved (w/ example).
- If $A$ is sorted in non-descending order, it is a valid minimum heap.
- If $H$ is represented by $A$, therefore $A$ is a sorted array in non-descending order.
- If $H$ is represented by $A$ (such that $A$ is the first element), then for any $2i < j$, the expression $A[i] < A[j]$ is true
- If $H$ is represented by $A$ (such that $A$ is the first element), then the following is a sorted array:
- If we sort each level in H separately, it will still be a valid minimum heap.
This was my proof:
true. Tested for with arrays $$, $[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.
false. $[10,50,40]$ is a valid minimum heap.
?. Apparently the answer is
falsebut any heap I tested worked.. So I don't understand how this could be false.
?. 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.
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!