Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@AJed, for min heap is possible see this, but for max heap is impossible(IMO). –  user742 Dec 5 '12 at 15:39
show 6 more comments

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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