0

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?

Community
  • 1
  • 1
user3437315
  • 270
  • 4
  • 13
  • 3
    The flaw is that the first k elements in the min heap may not be the k smallest (otherwise that would mean that the array is completely sorted). –  Nov 18 '14 at 17:16

1 Answers1

3

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.

Juan Lopes
  • 10,143
  • 2
  • 25
  • 44