Search code examples
c++sortinghashtable

finding top 10 elements in the hash table which contains 250,000 integer elements in C++

i want to find top 10 elements int the hash table. The hash table contains 250000 elements and these elements are only integer values. I dont want to sort the whole table. When i find the top 10 elements it is enough for me the rest is not important. What is the FASTEST(RUNTİME) way to do it? maybe heap sort? C++

Solution

  • I'll assume that the integers are in a collection you can iterate over.

    Imagine you need to find the single max element - you can iterate over the collection once keeping track of the largest element you have seen so far.

    Now modify the above approach for the top two elements you have seen so far.

    ...

    Now modify the above approach for the top ten elements you have seen so far.

    This "algorithm" has linear complexity which is as good as it gets. There are other ways of achieving linear time - all better then what you will get from Heapsort.