Question

Write pseudo codes for the function Change(A, heapsize, i, newValue) that accesses an element at the index i in the max-heap A (Note that the index of this heap starts from 1), and changes its value to the value of the parameter newValue, and also maintains its max-heap property. Note that newValue can be larger or smaller than the value of A[i]. You can use the heap functions/algorithms to implement this function. Also if the value of i is out of the range, then it should not change anything in the heap. void Change(A, heapsize, i, newValue)

Answer 1

Explanation:

The following pseudo-code for the function void Change(A, heapsize, i, newValue).

ALGORITHM:

STEP1: Define the function void Change(A, heapsize, i, newValue).

STEP2: Than find the maximum heap in an array A[i].

STEP3: Then index the following the right child, the left child and the parent.

maxheap property(A1 i)

maxright = left(i)

maxleft = right(i)

STEP4: Then, check the following condition, if maxleft <= A heapsize and [maxleft > A[i]].

then, laregest = i;

STEP5: Then, else

then, smallest = i;

STEP6: Then, check the condition, if maxright < = A heapsize.

then, largest = maxright;

STEP7: Set condition, if larger!= .

then, change A[i] with A[larger];

STEP8: Then built the maximum heap of an array element.

then, built - maxheap property (A)

then, A.heapsize = A.l

Set, if i = A.l/2 dowin to 1

then, maxheap property(A1 i)

STEP9: Then,  

void Change(A, heapsize, i, newValue)

{

if (indexi < o or index>=heapsize)

then, returm FALSE;

int old_val=heapA[index i].getkey()

heapA[index].setkey(new_val)

after that,  

if(new_val > old_val)

then, choose up the element in (index i)

else

then: choose down the element in (index)

return TRUE;

then call the function,  

Change()

STEP10: AFTER ALL, if the value of i is out of the range.

Then, change anything in heap A.