Problem 5.22. Design an algorithm find-in-heap(T[1..n],x) that looks for the val

Question

Problem 5.22. Design an algorithm find-in-heap(T[1..n],x) that looks for the
value x in the heap T and returns either the index of x in the heap, if it is present,
or 0 otherwise. What is the running time of your algorithm? Can you use the heap
property to speed up the search, and if so, how?

Problem 5.22 Design an algorithm find-in-heap(T [1..n],x) that looks for the value x in the heap T and returns either the index of x in the heap, if it is p or 0 otherwise. What is the running time of your algorithm? Can you use the heap property to speed up the search, and if so, ho

Explanation / Answer

Find-In-Heap(T[1..n],x)

for i = 1 to n

{

//loop from start of heap to end

if ( T[i] == x )

{

//if x found return i;

//return index of x

}

}

return 0;

// not found ,return 0.
}

This will take O(N) time.

Small Optimization can be made ,

Lets Take the case of (Max heap )
If we have found a node with the lower value than the element we are searching for then we dont have to search further because the element further to it will be smaller.

However, even with this optimization, search is still O(N)

We need to check N/2 nodes in average.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---