Member Avatar for ethio

If a heap is like a binary search tree shouldn't it search in O(log n)?

  • 2 Contributors
  • 1 Reply
  • 241 Views
  • 46 Minutes Discussion Span
  • Latest Post Latest Post by deceptikon
Member Avatar for 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).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.