2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.