Interview Question for Software Engineering at Palantir Technologies:

there is no need to implement this in min-heap as such .. one way to achieve this as it comes into my mind - devide the array into 100 smaller sets. Sort these smaller sets using, say counting sort / radix sort find the smallest in each set and that is what the result is supposed to be...if deviding it by 100 is still not reducing the size small enough then go one step further say 100^2. Then merge the smallest values in those sets to form an intermediary array .. a typical devide and conq. solution.