[Solved]: MinHeap represented by an array - two simple statements

Problem Detail: 

I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line.

These are the following statements:

Preface : Let A[n] be an array of min-heap (a min-heap represented by an array], whereas all the elements in the heap are different from each other. Let i and j be two indexes in the range : $0 \le i, j \le n-1$.

Prove or disprove :

1. If $i < j $ then $A[i] < A[j]$
2. If $A[i] < A[j] $ then $i < j$

I believe I managed to disprove both of them using the following heap:

$\qquad [2, 6, 7, 11, 14, 13, 12, 12, 13,15, 16, 71, 72, 13, 81]$

For:

1. Simply plug in the following indexes: $i = 4$ and $j = 13$.

   So $i < j$ but $A[i] > A[j]$.

2. Simply plug in the following indexes: $i = 13$ and $j = 4$.

   So $A[i] < A[j]$ but $i > j$.

Am I missing something here? Or It is really that easy?

Asked By : SyndicatorBBB

Answered By : Marc Khoury

You're not missing anything, this problem really is that easy. Your solution works, but I feel like I should point out that you can disprove both statements with a much smaller heap. In particular

\begin{array}{} [2, 7, 6] \end{array}

with $i = 1$ and $j = 2$ for the first statement and swapping them for the second.

Furthermore, I'm pretty sure those two statements only hold if the array is sorted (assuming distinct elements).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9444