During an interview, would it be recommended to try and implement quickselect in an interview, given that is O(N), even though it is a bit more difficult than using the heap method?
Also, for the heap methods, does it matter if we use the minheap method vs the maxheap method?
I think it depends on specific situations.
Using median to choose an pivot, it will get a better quickselect. This what the STL done. It's better than heap method. If the recursive is deep, the STL will using heap. And when N is less than a threhold(in VS, it's 32), STL will using insert sort.
When h > N/2，it's better to using maxheap, to reduce the times of removing the biggest number. Or, it's better to using minheap. Actually, the total time also depends on the time of building a heap.