a) We can use aheap to implement a priority queue. The Serve( ) function returns

Question

a)      We can use aheap to implement a priority queue.

The Serve( ) function returns the highestpriority item that will be the maximum heap element .TheEnqueue ( ) function inserts an input value intoheap. “Enqueue ( )” function first add a new node tothe tree. Then it traverses a path from this lead toward the rootto find a proper place for this new element.

Write pseudo code for Serve( ) andEnqueue ( ) function.

b)      Suppose H is amin heap containing n keys (elements). We want to write a functionprintSmaller() that prints all the keys in H thatare smaller than a given input key x .

Explanation / Answer

Dear User,    

ENQUEUE () function:

1) Insert an element (e) at the end of an array.

2) Find out the parent of this node [ R=ceil(i/2) ]

3) Find out its two children 2*R and 2*R+1

4) If 2*R== e then S=2*R+1 else S=2*R

5) If (e>S)

      {

         if (e>R)

            Swap e & R;

               Goto step 2

       }

     STOP otherwise

SERVE function:

Heapify the array

Return first element of the array (Heap)

b)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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