The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+33 votes
3.4k views

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 (59.7k points)
retagged by | 3.4k views
+1
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)
0
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 level.so 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".
0

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?

0
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).

2 Answers

+55 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.
answered by Boss (13.5k points)
edited by
0
@Anu yes
See here given " Suppose we perform a binary search on the path from the new leaf to the root "
Means we are performing binary search to know the path
Suppose it is A[12]---------> A[6]------------->A[0]
Now we know the path
So, next element inserted in A[13]
So, just put the element in A[13]
Why need to compare again in same path ?
0

The last statement from answer seems to be typeo:-

 this will be the n for binary search.

0
@rahul

it should be log n
0
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.
0
@flash

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
0

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

0
What would be the time complexity  if they asked about the time taken for insertion?
+1
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
0
@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
0
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??
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 (263 points)
Answer:

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

44,196 questions
49,668 answers
163,545 comments
65,817 users