retagged by
19,296 views
75 votes
75 votes

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:

  1. $\Theta(\log_2n)$

  2. $\Theta(\log_2\log_2n)$

  3. $\Theta(n)$

  4. $\Theta(n\log_2n)$

retagged by

5 Answers

Best answer
133 votes
133 votes
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$
edited by
10 votes
10 votes

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

5 votes
5 votes

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)

0 votes
0 votes

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  

 

Answer:

Related questions

31 votes
31 votes
8 answers
2
Kathleen asked Sep 21, 2014
25,770 views
A complete $n-ary$ tree is a tree in which each node has $n$ children or no children. Let $I$ be the number of internal nodes and $L$ be the number of leaves in a complet...
17 votes
17 votes
3 answers
3
33 votes
33 votes
4 answers
4