If a heap is like a binary search tree shouldn't it search in O(log n)?
deceptikon 1,790
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).