The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
83 views

Which data structure is most efficient to find the top 10 largest items out of 1 million items stored in file?

A

Min heap

B

Max heap

C

BST

D

Sorted array

asked in Algorithms by Loyal (5.5k points) | 83 views

1 Answer

+1 vote
Best answer

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 )

answered by Veteran (57.7k points)
selected by
0
Why not max heap?

To build max heap O(n) then to extract max will take O(log n)

BUT to sort array in descending/ascending order, best algorithm worst case O(nlogn).
0
brother, they already given it is sorted array ===> No need to sort again
0
I don't see anywhere they have mentioned that it is already sorted.
0
What is option D?

it is Sorted array but not unsorted Array
0
Yes, you are right.
0

why sorted array only? Please give explanation?

1->It's not given that array  is sorted increasing order/decreasing order?

2->It has some constant input (10M) and constant output than why are you comparing in order of O(n).  I think O(10M)=O(1).

3-> What is wrong with it? https://www.geeksforgeeks.org/data-structures-misc-question-2/ ,

https://www.careercup.com/question?id=5205121440940032

0

@Rustam Ali

i considered already they builds, Max Heap, Min Heap,BST and sorted array. then they want to find 10 largest elements

in https://www.geeksforgeeks.org/data-structures-misc-question-2/ i hope they consider option D as ARRAY not as Sorted array

if it really sorted array ===> my answer is true,

i gave the explanation why sorted array is better than Max Heap.

coming to min-heap ( explanation provided by geeks for geeks )

 

It's not given that array  is sorted increasing order/decreasing order?

By checking first two elements we can conclude it is sorted increasing order/decreasing order.

 

It has some constant input (10M) and constant output than why are you comparing in order of O(n). 

i didn't get this.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,725 questions
52,831 answers
183,519 comments
68,656 users