2

Possible Duplicate:
How we can find kth largest element from a max-heap in O(k) time?

There is a given a max-heap, we want to find an algorithm in o(k) time complexity to check if k'th smallest element is bigger than arbitrary given number.

Community
  • 1
  • 1
Pooria Kaviani
  • 748
  • 1
  • 8
  • 17
  • 1
    kth **smallest** element in a **MAX** heap? – UmNyobe Dec 05 '12 at 09:36
  • 1
    Is it max heap and smallest kth smallest element? Finding the smallest element in a max heap can be done in only `O(n)` AFAIK (you only know it is in one of the leaves). You can find the kth largest element in a max heap however in `O(k)` – amit Dec 05 '12 at 09:36
  • yes, Kth smallest element in a MAX heap – Pooria Kaviani Dec 05 '12 at 09:42
  • 2
    I don't want the kth largest element, I want an algorithm to check if kth smallest element is larger than arbitrary given number or not. – Pooria Kaviani Dec 05 '12 at 09:44
  • An algorithm in O(k), even O(klogn) doesnt exists. if you are using a max-heap it means the operation getMax() and deleteMax() are the most used... Otherwise use a min heap. – UmNyobe Dec 05 '12 at 09:52
  • @PooriaKaviani Actually your question is invalid. Of course the answer will depend on the actual data structure implementation. I suppose you mean if you implement the heap in a static array? Also can we destroy the structure of the heap when answering the query (i suppose not). – Boris Strandjev Dec 05 '12 at 09:52
  • Yes, we can destroy it, the given max-heap is in binary tree. – Pooria Kaviani Dec 05 '12 at 09:58
  • @SaeedAmiri: definitely it's not a duplicate of this question because here we are speaking about kth smallest, not largest element, and we are not required to find it. – Evgeny Kluev Dec 05 '12 at 10:41
  • @EvgenyKluev, You are right, I misread. – Saeed Amiri Dec 05 '12 at 10:45
  • 2
    REALLY? Why was it closed? It is NOT a dupe, it is entirely different question, asking for smallest k in max heap - not largest. **VOTING TO REOPEN** – amit Dec 05 '12 at 13:32

0 Answers0