The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+34 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)$

asked in DS by Veteran (52k points)
retagged by | 4.2k views
one extension to question is that even though comparisons can be done in O(loglogn) but still insertion will take O(n) time due to shifting elements down in O(n)
Max heap is the complete binary tree that means each node has either zero children or two children except the last level.
So in worst case inserting of an element is at last the number of comparisons required at each level starting from the root is equal to 1+2+4+8+16+---- this series is equal to "logn".

how complete binary tree?

take this as example

say 2 is newly inserted element

Now, n=8

So, if we take O(log n)=3

Now if we take O(loglog n)=2

So, is there only 2 comparison sufficient to find last inserted element?

Is this approach correct??--->>

For insertion in Max-Heap, worst case complexity is O(log n), and for binary search it is log n . Therefore , O(log log n).

@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

3 Answers

+58 votes
Best answer
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$
answered by Boss (13.2k points)
edited by

The last statement from answer seems to be typeo:-

 this will be the n for binary search.


it should be log n
what is meant by this?

Since in heap is a complete binary tree, in an array implementation, from every node index, we can know its depth and this will be the n for binary search.

when it is not a complete binary tree..there is a possibility of the binary tree being a skew tree and  when implemented as an array will not be proper....

but a heap is sure to be a complete binary tree and therefore the array implementation will have the positions of all the eements in the same order and sorted hence can be implemented using binary search

array elements may not be sorted all the times @ A_i_$_h.

What would be the time complexity  if they asked about the time taken for insertion?
it will be O(logn) as in insertion we need to increase the heap size and the we insert the new element in the last and perform heapify from bottom to top
@flash12 you are right every time the Max heap is not in a sorted way but in this question they said " we perform the binary search on the path from the new leaf to the root" it means that the element are in sorted order
Here we are applying binary search on 4 elements. But to know that we have to apply binary search on 4 elements we will need log(n) time. So final answer should be log(n)? Can someone please elaborate??

@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 ????

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  


answered by Junior (695 points)

@Rajesh Panwar

if you want to apply binary search then array should be sorted...

Max heap may not be sorted array...

example 10, 9, 8, 1, 2, 3 here how you apply binary search for finding position for newly inserted value?

in this question they are talking about binary search.
we cant't apply binary search always in heaps.
0 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)

answered by Active (1.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,576 questions
54,190 answers
71,147 users