search an element in a heap

Question

Hi

I remembered that heap can be used to search whether an element is in it or not with O(logN) time complexity. But suddenly I can't get the details. I can only find getmin delete add and so on.

Can anybody give a hint?

Answer 1

I think what you're looking for is a BST (binary search tree).

Answer 2

BST can be searched by O(logN), heap is used for sorting, not for searching.

Answer 3

You need to search through every element in the heap in order to determine if an element is inside.

One optimization is possible, though (we assume a max heap here). If you have reached a node with a lower value than the element you are searching for, you don't need to search further from that node. However, even with this optimization, search is still O(N) (need to check N/2 nodes in average).