GATE CSE 2007 | Question: 47

Question

Consider the process of inserting an element into a $Max \: Heap$, where the $Max \: Heap$ is represented by an $array$. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of $comparisons$ performed is:

• A. $\Theta(\log_2n)$

• B. $\Theta(\log_2\log_2n)$

• C. $\Theta(n)$

• D. $\Theta(n\log_2n)$

Comments

@srestha I think here we are required to find the worst case number of comparisons so in the worst case the new element will be inserted as a left child of node 4 in your graph(Assuming the previous level is full) so that there will be O(log log n) comparisons at worst. Am I correct? 

---

I am getting a doubt is binary search good for heap tree?

Here they told to do these operation, one after another

heap tree represent with an array$\rightarrow$insert an element$\rightarrow$do heapification in $\log n$ time$\rightarrow$then do binary search to find location of new element

---

*********************

First point we will find the position using binary search  so how will we apply binary search here see given it is represented in the form array when we insert an element in the end we will know the index  we need to do one thing in max heap is we will check with the the parent that is floor(current_index/2)  if we go on doing this until we get the root we will get all the and  on all these  LOGN  elements we can apply binary search until we find the position for logn elements it will take loglogn and for finding these indexes and getting those elements  each time each will take O(1)

**************************************

Answer 1

Time Complexity of Binary Search:Θ(logn)
where n is a number of elements.

Number of the element from root to new leaf is:logn

All the elements in the path from the root to new leaf is sorted then the time complexity to search position for newly inserted element is:Θ(loglogn)