In an interview, is it better to use a heap or use quickselect?

  • 0

    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?

  • 0

    I think it depends on specific situations.

    1. 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.

    2. 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.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.