You are given a MIN-HEAP with n keys represented by array A[1.. n ] ( length(A)=

Question

You are given a MIN-HEAP with n keys represented by array A[1..n] (length(A)=heapsize(A)=n). We would like to implement the following two operations on it: (a) DecreaseBy(A, i, k) that decreases the value of A[i] by k, i.e., the new value of A[i] will be A[i] = A [i] - k, (b) DeleteSpecific(A, i) that will delete element A[i] and thus eventually heapsize(A)=heapsize(A)-1. Give efficient algorithms that implement both operations correctly, and analyze their worst-case running time. Justify your arguments.

Explanation / Answer

(a) Algorithm for DecreaseBy(A, i, k)

DecreaseBy(A, i, k)

//Decreases value of key at index 'i' to val. It is assumed that val is smaller than A[i].

1. Assign A[i]=val

2. Swap A[i] with its parent until minheap property is restored

Worst case running time is: O(log n) because the maximum height of the tree is log n

.(b) Algorithm for  DeleteSpecific(A, i)

DeleteSpecific(A, i)

1. DecreaseBy(A, i, k)

2. Call method to remove minimum element (or root) from min heap named extractmin()

Function extractmin()

// Store the minimum value, and remove it from heap

Initialize int root = heaparray[0];

heaparray[A]=heaparray[heapsize(A)-1];

    heapsize(A)=heapsize(A)-1;

Call MinHeapify(0);

return root;

END FUNCTION

FUNCTION MinHeapify(int i)

ASSIGN int l = left(i);

ASSIGN int r = right(i);

ASSIGN int smallest = i;

IF (l < heapsize(A) && heaparray[l] < heaparray[i])

        smallest = l;

IF (r < heapsize(A) && heaparray[r] < heaparray[smallest])

        smallest = r;

IF (smallest != i)

        swap(&heaparray[i], &heaparray[smallest]);

        MinHeapify(smallest);

ENDIF

END FUNCTION

Worst case running time is: O(log n) because the maximum height of the tree is log n

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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