Problem 4 Let T be a heap storing n keys. Assume for this problem that the heap

Question

Problem 4 Let T be a heap storing n keys. Assume for this problem that the heap is stored in an array A starting from 1 that is, A] is the biggest key in the heap. Give an efficient algorithm for reporting all the keys in T that are greater than or equal to a given query key r (which is not necessarily in T). Note that the keys do not need to be reported (printed) in sorted order. Analyse the running time. An O(k) algorithm is needed for full grade, where k is the number of elements printed. That is, the algorithm should do a constant number of elementary operations per printed element

Explanation / Answer

The function keys can be used to solve the purpose:

void keys(int x,int i)

{

if(x>A[i] or i>n) return;

else

{

printf("%d ",A[i]);

if(A[2*i]>=x)

keys(x,2*i);

if(A[2*i+1]>=x)

keys(x,2*i+1);

}

return;

}

Call keys in your code as keys(x,1);

This function will be executed k number of times(where k is the number of elements printed).

In this function we are checking initially if A[1] > x and then we are checking for its children and then children of children and so on. We are checking each element just once and not checking the children of element for which x > A[i] (for ith element). So we will check only k elements and print them.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.