Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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