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

Number of elements in the path from new leaf to root $= \log n$, and all elements are sorted from leaf to root so we can do a binary search which will result in $O(\log \log n)$ number of comparisons.

Since a heap is a complete binary tree (hence height balanced also), in an array implementation, from every node index, we can know its depth and this will be the number of elements $-$ $n$ for binary search.

Correct Answer: $B$

Comments

@Shaik Masthan

 

What will be time complexity for inserting not only searching position..

To find correct index we copy elements in new array which are on path from leaf node to root node ..and as those elements will be sorted we can apply binary search to find position..but this is all happening in new array..after finding to insert back to  max heap array how long does it takes ????

---

How can it be loglogn ...?

we are applying binary search when we are finding the parents to compare the inserted node with its parents .

we are doing i/2 every time...you can not apply binary search on this now... answer to this question is logn only.

---

Only one element search using binary search we required o(logn), but there are logn elements between newly inserted node hence, for checking logn element we need 0(loglogn) comparison.

Answer 2

Given this max-heap:

                               100
                              /    \
                            80       90
                            /\       /\
                           50 40    70 60

You know that the new element, 250, must be inserted somewhere along the path [100, 80, 50]. You know that because in the standard heap insertion method, you add the new item in the first free position in the array and then sift it up the heap. In this case, you'll be adding it at position 7, and the path to the root is 7 -> 3 -> 1 -> 0.

If you apply a binary search to determine where along that path the item will be inserted, you'll discover that it must be before the value 100.

I think the question is designed to test your knowledge of the heap's properties. In a heap of n items, there are log(n) levels. Let's call that value h. The path from the root to an item on the last level will contain h items. Binary search is known to be O(log n). Or, in this case, O(log h). And since h == log(n), the answer is O(log log n). source arrays - Insertion of a new element in Binary Max Heap - Stack Overflow

Answer 3

When we insert single element in heap using binary search to find position of new element instead of linear search. Then

Maximum number of comparison is log(h), Where h is height of tree.

we know that height of heap h = log n.

Hence, number of comparisons = Θ(log log n)

Answer 4

Ans- Option B

first find the length of tree it will take O(log n) time 

and after applying binary search on path it will take  O(log(log n)) time  

 

Comments

You have indices of the array elements (MAX HEAP)( from newly inserted node to root) stored in a new array  for worst case structure , now you have a sorted array and we can apply binary search ,now one should answer how many elements does the new array have ? 

We have log(n) elements stored in the newly created array , applying B-search will lead to Time Complexity of O(log(logn))

---

:) thanks your comment made me understand everything

---

Can you explain how does apply binary search on newly created array will help us to find the position of the newly inserted element?