GATE Overflow Test Series | Algorithms | Test 1 | Question: 8

Question

Consider the binary tree shown below, which is an almost max-heap with the node $22$ violating the max-heap property. Once heapify procedure is applied to it, which position will it be in?

 

Answer 1

We need to perform swapping, to get max-heap.

Swapped $22$ and $42,$ we get

Swapped $22$ and $26,$ we get max-heap.

So, the correct answer is $9.$

Answer 2

$22$ and $42$ will get swapped. Then $22$ and $26.$ So, final position of $22$ will be $9.$