O(k) algorithm to find kth min element from a min heap

1.4k Views Asked by At

o(klogn) solution is trivial to find the kth minimum.And here O(klogk) time algorithm to find kth smallest element from a binary heap is a O(klogk) solution. But i was thinking of an algo which could be o(k) if correct . From the min heap,take the first k elements(first k nodes,traverse level wise ) and store them in an array .Now max heapify this array bottom-up which would take o(k) time.The root of this heap would be the required answer.Can anyone see a flaw in this algorithm?

1

There are 1 best solutions below

0
On

Consider this example

        1
    2       11
  3   4   12  13

If you want to get the 3rd min element, it wouldn't be in the 3 first nodes.