Find Element in Max Heap

Question

I have a MaxPQ Heap that uses an array to store the elements. What is an algorithm I could use to find a given element in the heap ? The algorithm I am currently using iterates through the array starting with the index 1 and upto the number of elements added to the heap. This algorithm has a complexity of O(N), is there an algorithm with complexity O(logN) ?

Solution

If you have only an array representing a heap (min or max) than I'm afraid a worst-case logarithmic algorithm is not to be found, since starting at the top of the tree you aren't going to be able to tell in general which subtree to search. If your root is 100 and its children are 90 and 80, and you are looking for a 5, you've got to (in general) explore both paths.

Now if you keep an auxiliary data structure around which tracks the position in the array of your keys, you can hack in a constant time lookup. I found the following description at http://eclipse.wells.edu/badams/courses/cs322/notes/topics/tools/heap.html

To find an arbitrary element, it helps to maintain an additional array indexed by node names and keyed by their position in the heap (either a pointer, or an index number). That makes lookup of an arbitrary node work in constant time, and maintaining the data in the array only requires a fixed number of steps for each bubbling operation, so doesn't change the asymptotic time for heapify up or down.

Again, given just the heap, your worst-case will be linear, though you might get a little bit of a speedup in practice if you traverse the heap and do some pruning.