retagged by
765 views

1 Answer

3 votes
3 votes

Answer : A (Assuming in the Question He meant Just Heap or Max Heap)

First we will find $p_i/w_i$ for each item which will take $O(n)$ time.

Then, We will build a Max Heap (not Min Heap) based on parameter $p_i/w_i$ which will take $O(n)$ time.

then we will delete the Root(max item) one by one ($O(logn)$ time) and do some calculation ($O(1)$ time). So, for $n$ items, $O(nlogn)$ time.


but If we implement it with min heap data structure then $O(n^2)$. Because It takes $O(n)$ to find max in Min-heap.

edited by

Related questions

9 votes
9 votes
2 answers
1
vineet.ildm asked Nov 7, 2016
5,807 views
Why space complexity of heapsort is O(1)....and why not O(logn)..because of space required by recursion calls which is equivalent to height of the tree...where am i getti...
1 votes
1 votes
1 answer
2
reena_kandari asked Jul 30, 2016
987 views
The number of elements that can be sorted in time using heap sort ?
0 votes
0 votes
0 answers
4