4 Years
Discussion Span
Last Post by deceptikon

A heap is like a binary search tree, but it isn't one. The heap property is less strict in that you can't tell from the current node whether to search the left or right subtree.

All you know is that the item in the current node is a match, couldn't possibly be in one of the subtrees (because it would have been higher than the current node), or the item exists in one of the subtrees. Therefore you have no choice but to search every node in one way or another. General search gives you an average case of O(N/2), which reduces to O(N).

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.