157 views
$(1)$ In a binary heap with $'n'$ elements with the smallest element at the root, the $7th$ smallest element can be found in time?

$A)\theta(nlogn)$            $B)\theta(n)$              $C)\theta(logn)$             $D)\theta(1)$

$(2)$ In binary max heap containing $'n'$ numbers, the smallest element can be found in time?

$A)\theta(n)$                $B)\theta(logn)$          $C)\theta(loglogn)$          $D)\theta(1)$

$(3)$ Consider the process of inserting an element into a max heap. If we perform a binary search on the path from new leaf to root, find the position of a newly inserted element, the number of comparisons performed are____________

$(4)$ We have a binary heap on $'n'$ elements and wish to insert $'n'$ more elements(not necessarily one after another) into this heap. The total time required for this is?

$A)\theta(logn)$           $B)\theta(n)$              $A)\theta(nlogn)$                      $A)\theta(n^{2})$
0
Yes right
0
1) d

2)a

3) log log n

4) b
0
For $(1) C$
0
In 1 question

you are just finding not deleting
0

Not find smallest(minimum), we need to find $7th$ smallest.

0
That's what i got confused earlier :)
0
To find 1 smallest it will take 1 comparison

to find 2 smallest

2 smallest is either the left child of root or right  child of root

For 3 smallest only 3 elements are participating in competition i e left child of 2 smallest or right child of 2 smallest or looser of 2 level

in this manner by constant conparison we can find the kth smallest in O (1) time
0
we need to delete 6th min then find 7th min.
0
0
Yes you are right but it is taking log n time but a better way is possible which is taking constant time so go for that one

1
+1 vote
2