Search an element in a heap

algorithm data-structures heap big-o
skydoor picture skydoor · Mar 3, 2010 · Viewed 66.4k times · Source

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

Anonym Mus picture Anonym Mus · Mar 3, 2010

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).

Related questions

How to delete in a heap data structure?

I understand how to delete the root node from a max heap but is the procedure for deleting a node from the middle to remove and replace the root repeatedly until the desired node is deleted? Is O(log n) …

Read More
Max-Heapify A Binary Tree

This is one of the interview questions I recently came across. Given the root address of a complete or almost complete binary tree, we have to write a function to convert the tree to a max-heap. There are no arrays …

Read More
O(klogk) time algorithm to find kth smallest element from a binary heap

We have an n-node binary heap which contains n distinct items (smallest item at the root). For a k<=n, find a O(klogk) time algorithm to select kth smallest element from the heap. O(klogn) is obvious, but …

Read More