10 maximum integers from 1 million integers

You Have File of Containing 1 Million Integers You need To Find 10
Maximum Integer Out of Them.How You Will Do That. What is Time &
space Complexity of Algorithm that you will use then optimize the
solution..

Constraints- U can't Store Whole File in memory at one time.

Strategy:

Using Min Heap:

Use a min-heap of 10 elements.Initialize the heap with first 10 elements in O(10) [constant] time.For each of the next element,check whether it is greater than root of min heap,if it is,replace that element by the next element and heapify the heap again in O(log10) [constant] time.At last extract all the 10 elements one by one in O(log10) constant time each.so space complexity O(1) time complexity O(N).

Using Max Heap:

A solution for this problem may be to divide the data in some sets of 1000 elements (let’s say 1000), make a heap of them, and take 10 elements from each heap one by one. Finally heap sort all the sets of 10 elements and take top 10 among those. But the problem in this approach is where to store 10 elements from each heap. That may require a large amount of memory as we have billions of numbers.

Reuse top 20 elements from earlier heap in subsequent elements can solve this problem. I meant to take first block of 1000 elements and subsequent blocks of 990 elements each. Initially heapsort first set of 1000 numbers, took max 10 elements and mix them with 990 elements of 2^ndset. Again heapsort these 1000 numbers (10 from first set and 990 from 2^nd set), take 10 max element and mix those with 980 elements of 3^rd set. Repeat the same exercise till last set of 990 (or less) elements and take max 20 elements from final heap. Those 10 elements will be your answer.

Complexity: O(n) = n/1000*(complexity of heapsort 1000 elements)

Since complexity of heap sorting 1000 elements will be a constant so the O(n) = N i.e. linear complexity