# Determine whether the $k^{th}$ smallest element in max-heap is greater than a given number

A set of numbers is stored in a max-heap. We want to find an algorithm with $O(k)$ time complexity to check if $k^{th}$ smallest element is greater than an arbitrary given number.

• o(k) and O(k) mean different things. Do you actually mean O(k) instead? – usul Dec 5 '12 at 9:35
• Is the question about how do we implement such a heap, or is that, given a max-heap, how do we answer the question? If the second one, what do we know about the max-heap -- what operations can we do and what are their time complexities? – usul Dec 5 '12 at 9:36
• no, the heap is given. max-heap is a tree we can move on its elements. – Pooria Kaviani Dec 5 '12 at 9:41
• excuse-me, I mean O(k). – Pooria Kaviani Dec 5 '12 at 9:44
• @AJed, for min heap is possible see this, but for max heap is impossible(IMO). – user742 Dec 5 '12 at 15:39

Suppose we have a max-heap of $n$ elements such that $k<\log n$ and I inform you that the $k^{th}$ smallest element is at the greatest depth of the tree. Without this detail, it could be elsewhere in the tree, but if we cannot solve this special case in time $O(k)$, the more general case will take at least as much time - otherwise, we could use the algorithm for the general case to solve this specific case.
Note that in a max-heap, no node will give a bound on how small its children will be (but rather only how large). Thus, if we know the $k^{th}$ smallest is at the greatest depth, no node except those at the greatest depth will provide any information as to the location of the $k^{th}$ smallest element. There are $\log n$ children at the greatest depth and no particular ordering among them (which is one of the key characteristics which differentiates a heap from a sorted binary tree). Thus, you'll need to check all $\log n$ elements before you can determine whether the $k^{th}$ smallest is greater than an arbitrary number.
Hence, no comparison based algorithm with time complexity less than $O(\log n)$ exists to determine for a given max-heap whether the $k^{th}$ smallest element is greater than an arbitrary number.