Max heap vs Min heap for kth smallest element

Admin 1
Viewed 1730

I am having trouble understanding why solutions for finding the kth smallest element uses a Max heap approach. And for the kth largest element a min heap approach. Wouldn't it make more sense to use min heap to find kth smallest element, since the smallest element will always be root? So if we want to find the 3rd smallest element, then we just delete the root 2 times, build the heap, and we get the 3rd smallest. In a max heap the smallest is not at the root, so why is it better to use? The same goes for sorting in ascending or descending numbers in an array. I see most people use max heap for ascending.

min-heap max-heap heapsort heap algorithm
1 Answers

In fact, we can use both Min and Max heap to find the k-th smallest element:

  1. Just like you described, we can build a Min Heap, and then extract k-th element in a loop.

or

  1. We can build Max Heap with just k elements. Then we just compare the rest of the elements with the root, substituting with the root only elements which are smaller than the root, so the Max Heap has always k smallest elements.
user_79699000
Related