Question No:2 a) We can use a heapto implement a priority queue. The Serve( ) fu

Question

Question No:2                                  

a)      We can use a heapto implement a priority queue.

The Serve( )function returns the highest priority item that will be the maximumheap element .The Enqueue ( ) function inserts aninput value into heap. “Enqueue ( )” function first adda new node to the tree. Then it traverses a path from this leadtoward the root to find a proper place for this new element.

Write pseudo code forServe( ) and Enqueue ( )function.

b)     Suppose H is a min heapcontaining 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

ENQUEUE () function:

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

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

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

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

STEP 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 Q
• Subjects

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