Find Kth largest element in Heap

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage

==========================

thats the question, i cant never figure out how to make it to work in O(k) time...

please help!

O(k log k) is easy: just do the "find maximum" operation k times.

O(n) is even easier: just look at each element; either you'll find k that are greater than x, or you won't.

O(k) is a little trickier, but not too bad. It builds off the O(n) solution, making use of the fact that the heap is heap-ordered. The crucial "atom" of the algorithm is this piece of reasoning:

• If I look at a node and its value is greater than x, then I just found another node with value greater than x. On the other hand, if its value is less than or equal to x, then the same must be true for every node in the entire subtree of that node.

That leads very naturally to breadth-first-search. (That's where the O(k) auxiliary storage comes in.)

I haven't been completely explicit, but hopefully that's enough for you to figure it out. Keep in mind that you do not actually need to find the kth largest element (as the thread title states); you only need to determine if there are k elements > x