-1
$\begingroup$

In the binary tree shown below, which of the following trees is created after conversion into a (max) heap?

enter image description here

There are 4 anwsers to choose :

enter image description here

By definition, a max heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node., so a, c, d are all correct, but there is only one correct anwser!

What am i missing here ?

$\endgroup$
1
  • 1
    $\begingroup$ Other than the typo, a very nice question. Option b with the typo corrected is the one you want. The key here is to move each node into its place, starting within the smaller sub-tree. $\endgroup$ – InformedA Oct 13 '14 at 5:23
1
$\begingroup$

There is a typo in your options. In option (b) the root should be 16 not 1. The tree thus formed is the correct answer.

To get it from your original tree do this

for i = floor(Array.Length/2) down to the first element: Max-Heapify(Array,i)

$\endgroup$
3
  • $\begingroup$ Thanks for the answer, option B is the correct one indeed, but what I don't get is, the others also satisfy the condition each internal node is greater than or equal to the values in the children of that node ? Why are they wrong? $\endgroup$ – f855a864 Oct 13 '14 at 5:14
  • $\begingroup$ They do but they havent been converted from the given tree. $\endgroup$ – user22148 Oct 13 '14 at 5:18
  • $\begingroup$ ahh, I misread the question again! Thanks! $\endgroup$ – f855a864 Oct 13 '14 at 5:54

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.