Suppose that binary heaps are represented using explicit links. Consider the pro

Question

Suppose that binary heaps are represented using explicit links. Consider the problem of merging binary heap lhs with rhs. Assume both heaps are perfect binary trees, containing 2l 1 and 2r 1 nodes, respectively. a. Give an O(logN) algorithm to merge the two heaps if l = r. B). Give an O(logN) algorithm to merge the two heaps if |l r| = 1. C. Give an O(log2 N) algorithm to merge the two heaps regardless of l and r I COULDNT GET THE SOLUTION FOR PART B AND PART C ALSO I DONT NEED A THEORITICAL EXPLAINATION COZ I NEED IT WITH AN EXAMPLE IMPLEMENTING THREE SCENARIOS

Explanation / Answer

Binary Heap:

a) The algorithm O(log N) for merging the two sub trees when the left sub tree is equal to right sub tree is,

int FndMinimum(PriQueue Hp)

{

if(!IsEmp (Hp))

return Hp -> Elems[1];

Err("The Priority Queue is now Empty.");

return Hp -> Elems[0];

}

int DelMinimum(PriQueue Hp)

{

int x, Child;

int MinElement, LastElement;

if(IsEmp(Hp))

{

Err("Priority queue is empty");

return Hp -> Elems[0];

}

MinElements = Hp -> Elems[1];

LastElement = Hp -> Elems[Hp -> Sz--];

for (x=1; x*2 <= Hp -> Sz; x=Child}

{

Child x*2;

if(Child != Hp -> Sz && Hp -> Elems [Child+1] < Hp -> Elems[Child])

Child++;

if (LastElement > Hp -> Elems[Child])

Hp -> Elems[x] = Hp -> Elems[Child];

else

break;

}

Hp -> Elems[x] = LastElement;

return MinElement;

}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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