3.1k 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)$

retagged | 3.1k 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).

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.6k points)
edited
+4

Why there is need to search before added to heap?

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

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