Top 100 algorithm
-
Let's say you need to find the top 100 best-selling books out of a list of a million books. What is the appropriate algorithm? I thought it would be QuickSelect, but that only chooses one item. Thank you.
-
Let's say you need to find the top 100 best-selling books out of a list of a million books. What is the appropriate algorithm? I thought it would be QuickSelect, but that only chooses one item. Thank you.
If you don't want to sort the list, for whatever reason, you could always use a Max Heap structure with a heap size of 100. Iterate over your books and, if the new book has higher sales than a book in the heap, replace the bottom element with the new one. This assumes that no two book sales are going to be the same, so you would have to consider that particular wrinkle. In .NET for instance, you can use the
PriorityQueueclass to handle max heaps.