CODEWITHSUNDEEP
arrayscalgorithmminimum
nonlegalacc
nonlegalacc

Reputation: 19

Without sorting finding minimum 10 elements in array

I need to find the ten minimum elements in an array which has 1000 unordered numbers. I firstly think like: sort it and select first ten element but my duty is doing the same thing without sorting. By the way I am using C programming. Can you help me?

Upvotes: 1

Views: 631

Answers (1)

user1984
user1984

Reputation: 6788

Using a max heap of size 10 you can achieve this in O(n * log(10)) = O(n) time complexity as follows:

  1. Initialize a max heap, hp.
  2. Add the first 10 elements of the input array to the heap.
  3. Iterate over the remaining elements of the input array and do the following for each one of them:
  • Compare the element with the element at the tip of the heap.
  • If it's smaller, pop one from the heap and push the element onto the heap.
  1. At the end of the loop, you have a heap that holds the 10 smallest elements of the input array. The element at the tip of the heap, is the 10th smallest.

Upvotes: 5

Related Questions