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.

  • $\begingroup$ o(k) and O(k) mean different things. Do you actually mean O(k) instead? $\endgroup$
    – usul
    Dec 5 '12 at 9:35
  • $\begingroup$ 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? $\endgroup$
    – usul
    Dec 5 '12 at 9:36
  • $\begingroup$ no, the heap is given. max-heap is a tree we can move on its elements. $\endgroup$ Dec 5 '12 at 9:41
  • $\begingroup$ excuse-me, I mean O(k). $\endgroup$ Dec 5 '12 at 9:44
  • 1
    $\begingroup$ @AJed, for min heap is possible see this, but for max heap is impossible(IMO). $\endgroup$
    – user742
    Dec 5 '12 at 15:39

Here is an attempt at disproof:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.