21,499 views
41 votes
41 votes

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

  1. $\Theta(\log n)$

  2. $\Theta(n)$

  3. $\Theta(n\log n)$

  4. $\Theta(n^2)$

7 Answers

Best answer
72 votes
72 votes

An insert operation on a binary heap takes $\mathcal{O}(\log n)$ time, but an alternative approach we can use. which requires us to insert $n$ elements in heap without any computation i.e. in constant time. after which we can apply Heapify operation(this operation creates heap in linear time) on the array of those element and Hence obtain a Heap in $\mathcal{O}(n)$ time.


Here "not necessarily one after another" should mean that we can insert $n$ elements at once and not necesaairly have to wait for first insert to be completed before doing second.

Correct Answer: $B$

edited by
12 votes
12 votes
Answer is B.

By build Heap method.
8 votes
8 votes
to insert 1 element into heap it will takes O(logn) time,

so to insert n elements into heap it will take O(nlogn) time.

but there is also a better way means we can apply build heap method for 2n elements it will take O(2n) =O(n).

so b is ans
Answer:

Related questions

79 votes
79 votes
7 answers
3
Kathleen asked Sep 12, 2014
36,301 views
The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is$\Theta(n)$$\Theta(\log n)...
28 votes
28 votes
6 answers
4
Kathleen asked Sep 11, 2014
13,236 views
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity$\Theta(n)$$\Theta(m)$...