recategorized by
2,846 views

1 Answer

Best answer
1 votes
1 votes

if your no.of elements are fixed, then most efficient Data structure is Sorted array ( my concentration is only on finding top ten largest elements )

How?

1) Max Heap :- ( take root level as 0 )

 we can't guarantee that "TOP ten elements should be in 9th level, but we can guarantee  those are should be below 10th level ===> total no.of elements check is 1023 elements"

 

2) Min Heap :- ( take root level as 0  and take total k levels)

 we can guarantee that "TOP ten elements should be in last level ( no.of elements in last level should be > 10 ),  total no.of elements check is 2k-1 elements"

 

3) BST, it is not balanced,

what happens if it is balanced? then we can find the 1st largest element in O(1) but what about remaining?

we should check more than half of the elements of the ( right sub tree of the root )

selected by

Related questions

0 votes
0 votes
2 answers
2
Rustam Ali asked Sep 3, 2018
855 views
Find time complexity of below Program?A(n){if(n<=1) return;elsereturn $A(\sqrt{n})$ ;}