1
$\begingroup$

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: enter image description here
  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!

$\endgroup$
2
  • $\begingroup$ Please ask only one question per post. This has 5 questions. $\endgroup$ – D.W. Jun 18 at 19:46
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. We prefer you ask about a specific conceptual issue you're uncertain about. As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jun 18 at 19:46
1
$\begingroup$

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!

$\endgroup$
11
  • $\begingroup$ About 1, I didn't really understand your statement about "definition of the minimality". About 3, I would assume that's what they meant, and then it's obviously true. But I thought maybe it was a trick. For example $2log(n=8)-1\rightarrow A[5]$. Thank you for 3 though, really helped me out! $\endgroup$ – Alex Osheter Jun 18 at 14:20
  • 1
    $\begingroup$ A heap represented by an array is such that the two children of the node with index $i$ are the nodes with indices $2i$ and $2i+1$. Since its a minimal heap, then their value is at least as large as the value of the node $i$, hence $A[i]\le A[2i],A[2i+1]$ $\endgroup$ – nir shahar Jun 18 at 14:22
  • $\begingroup$ Ahhh right right. Thank you! $\endgroup$ – Alex Osheter Jun 18 at 14:25
  • $\begingroup$ Glad that I can help :) $\endgroup$ – nir shahar Jun 18 at 14:27
  • $\begingroup$ What do you think they meant with 4 though? As I've shown, $2*log(n)-1$ couldn't have been it. Since the path to a leaf would produce $A[1], A[2], A[4], A[5], A[7], ...$ $\endgroup$ – Alex Osheter Jun 18 at 15:33

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.