0
$\begingroup$

Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the property of a max-heap doesn't really help us unlike a bst. Thanks.

$\endgroup$
  • $\begingroup$ Yes, it is $O(\log n)$ time in the worst case. Assume you have some arbitrary strategy in order to find some specific element. Then you can easily think of a heap in which the element you are searching for is the last one you are looking at. $\endgroup$ – user1742364 Mar 20 '15 at 9:47
  • 2
    $\begingroup$ but for a max heap property: the parent has the highest value...Can't we end up searching every element? $\endgroup$ – Bobby Hill Mar 20 '15 at 9:54
  • 2
    $\begingroup$ @user1742364 That's wrong; there is no such strategy. $\endgroup$ – Raphael Mar 20 '15 at 11:13
5
$\begingroup$

You are correct: it's $\Theta(n)$ in the worst case. Suppose you're looking for something that's no bigger than the smallest value in a max-heap. The max-heap property (that the value of every node is at least as big as everything in the subtree below it) gives you no useful information and you must check both subtrees of every node.

$\endgroup$

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.