The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+31 votes
2.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 (69k points)
retagged by | 2.4k 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 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".

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?

1 Answer

+47 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 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.
answered by Veteran (14.1k points)
selected by
We know the indices of the path from root to leaf. Now, we can start from the middle of these indices and consider these indices as another array which will be used for indexing into the original array for binary search.
Yes, it's right.
Only for search loglogn ,if we actually insert it will go to logn only i think

due to swaps.for this ques only search so loglogn.
Its Max/Min heap. Not a mere array. Depth will be logn
Can we apply the binary search directly or we have to copy all the elements into a new array as the indices will be 1,2,4,8,16...

I think we can not apply the binary search directly
Yes. All the elements of the path have to be copied in a new array.
if we implement this metho for heapify no of comparison=loglogn nd no of swap=logn ?
yes....
Why not log n?

It could be last element of the heap

So, inserting time can be nlogn, where we nee to search every element of heap

like this

@srestha they are asking just number of comparison, not TC.

 

@ Shubhanshu

they represented it asymtotic format

Why there is need to search before added to heap?

addition will take O(logn) time not O(nlogn).

 

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

The last statement from answer seems to be typeo:-

 

 this will be the n for binary search.

@rahul

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

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

 



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

33,687 questions
40,230 answers
114,268 comments
38,790 users