-2
$\begingroup$

Can someone give me the best search algorithm in a max heap?

In particular simply implemented as an array. I knew it has complexity of $O(N)$ but it can be done better. For example, if $A[i] < \mathrm{key}$ it's useless to search in the sub-tree with that root in the $i$th position.

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome to CS.SE! "best" is subjective, so we usually discourage asking for the "best" anything. Instead, it's better to list your requirements or the criteria you'll use for evaluating answers. Do you want fastest asymptotic running time? Fastest in practice? Easiest to code? Something else? If you don't tell us in the question, you force us to guess. $\endgroup$
    – D.W. ♦
    Commented Apr 6, 2016 at 6:00

1 Answer 1

Reset to default
1
$\begingroup$

Since you don't state otherwise, I assume you are interested in worst-case performance.

Your claim "it can be done better [than $\Theta(n)$]" is plainly wrong¹; if the desired key $x$ is on the lowest level but all keys on the second-to-lowest level are larger than $x$, you'll not be able to skip any subtree.

  1. Assuming we have a "plain" binary max-heap and the algorithm would work as you suggest. For a more general statement we'd have to fix the exact heap implementation and invest more work to prove a lower bound.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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