algorithm - Top n elements in queue -


i have implemented queue using 2 stacks , want find top n percent elements in queue.

for example:
queue takes element in order {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

top 10% elements means 10% of 20 = 2

hence answer should 19 , 20

there 2 ways can think of

  1. sort queue, claculate number of items (x) n% , grab top x elements.
  2. selection algorithm. (i came across algorithm , based on idea of quicksort. have copy entire queue array , apply algorithm)

is there better way solve this?

a queue isn't best data structure that, should not access elements inside (most of queue implementations don't provide access operator) shouldn't sort it. so, if don't need queue due other requirements, suggest use plain array.

sorting time consuming process. read/insert queue elements can compute sum. based on known sum, number of elements , percent required, can compute threshold. then, need iterate through elements (if using queue, can extract them 1 one) , display greater computed threshold.


Comments

Popular posts from this blog

javascript - how to protect a flash video from refresh? -

visual studio 2010 - Connect to informix database windows form application -

android - Associate same looper with different threads -