Skip to main content
Software Engineering

Return to Question

replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link
Community Bot
Community Bot
  • 1

I have an array with a large number of elements, and I need to find the k largest elements.

For an idea of scale, let us assume an integer array of length 10,000,000, and k is 1,000.

I see three potential solutions:

  1. This answers to this question on Stack OverflowThis answers to this question on Stack Overflow suggest the selection algorithm to find the kth largest integer, Then perform a partition to find all elements larger than that value.

  2. A Min Heap with a max size of 1000 could also be used. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n log k). What is the average case?

  3. I could use a selection sort algorithm to find the max k times and put it on the right of the array. This solution seems like it would have a worst case of O(n*k).

Which of these solutions would you expect to perform best on my data set?

I have an array with a large number of elements, and I need to find the k largest elements.

For an idea of scale, let us assume an integer array of length 10,000,000, and k is 1,000.

I see three potential solutions:

  1. This answers to this question on Stack Overflow suggest the selection algorithm to find the kth largest integer, Then perform a partition to find all elements larger than that value.

  2. A Min Heap with a max size of 1000 could also be used. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n log k). What is the average case?

  3. I could use a selection sort algorithm to find the max k times and put it on the right of the array. This solution seems like it would have a worst case of O(n*k).

Which of these solutions would you expect to perform best on my data set?

I have an array with a large number of elements, and I need to find the k largest elements.

For an idea of scale, let us assume an integer array of length 10,000,000, and k is 1,000.

I see three potential solutions:

  1. This answers to this question on Stack Overflow suggest the selection algorithm to find the kth largest integer, Then perform a partition to find all elements larger than that value.

  2. A Min Heap with a max size of 1000 could also be used. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n log k). What is the average case?

  3. I could use a selection sort algorithm to find the max k times and put it on the right of the array. This solution seems like it would have a worst case of O(n*k).

Which of these solutions would you expect to perform best on my data set?

Tweeted twitter.com/StackSoftEng/status/813073678116253696
Rewrote for better clarity.
Source Link
user22815
user22815

My question pertainsI have an array with a large number of elements, and I need to what isfind the best way to "Find k max integers of an array"k largest elements.

If it helps any lets say we are looking for the max 1000 numbersFor an idea of scale, let us assume an integer array withof length 10,000,000.

I have found, and this answer that sugests the selection algorithm to find the kth largest integer. Then you would do a partitionk is 1,000.

The other solution would be to set up a Min Heap with a max size of 1000. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n * (1 + log k)) or O (n log k). What is the average case?see three potential solutions:

  1. This answers to this question on Stack Overflow suggest the selection algorithm to find the kth largest integer, Then perform a partition to find all elements larger than that value.

  2. A Min Heap with a max size of 1000 could also be used. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n log k). What is the average case?

  3. I could use a selection sort algorithm to find the max k times and put it on the right of the array. This solution seems like it would have a worst case of O(n*k).

Another solution would be to use a selection sort algorithm where you find the max k times and put it on the rightWhich of the array. This solution seems like itthese solutions would have a worst case of n*k.

Can you go into detail about why a min heap's average case is better or worse than the other solutionsexpect to perform best on my data set?

My question pertains to what is the best way to "Find k max integers of an array".

If it helps any lets say we are looking for the max 1000 numbers of an array with length 10,000,000.

I have found this answer that sugests the selection algorithm to find the kth largest integer. Then you would do a partition.

The other solution would be to set up a Min Heap with a max size of 1000. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n * (1 + log k)) or O (n log k). What is the average case?

Another solution would be to use a selection sort algorithm where you find the max k times and put it on the right of the array. This solution seems like it would have a worst case of n*k.

Can you go into detail about why a min heap's average case is better or worse than the other solutions?

I have an array with a large number of elements, and I need to find the k largest elements.

For an idea of scale, let us assume an integer array of length 10,000,000, and k is 1,000.

I see three potential solutions:

  1. This answers to this question on Stack Overflow suggest the selection algorithm to find the kth largest integer, Then perform a partition to find all elements larger than that value.

  2. A Min Heap with a max size of 1000 could also be used. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n log k). What is the average case?

  3. I could use a selection sort algorithm to find the max k times and put it on the right of the array. This solution seems like it would have a worst case of O(n*k).

Which of these solutions would you expect to perform best on my data set?

Source Link
user3795202
user3795202
  • 41
  • 2

Find k max integers of an array -- Min Heap vs. Selection Algo vs. Selection Sort

My question pertains to what is the best way to "Find k max integers of an array".

If it helps any lets say we are looking for the max 1000 numbers of an array with length 10,000,000.

I have found this answer that sugests the selection algorithm to find the kth largest integer. Then you would do a partition.

The other solution would be to set up a Min Heap with a max size of 1000. If the heap is full when you attempt to insert you remove the min and add your new element. Doing this for one element would be average O of 1 for the insert and O of log(n) for the remove (if necessary). So I guess worst case would be something like O(n * (1 + log k)) or O (n log k). What is the average case?

Another solution would be to use a selection sort algorithm where you find the max k times and put it on the right of the array. This solution seems like it would have a worst case of n*k.

Can you go into detail about why a min heap's average case is better or worse than the other solutions?