6.5-8

6.5-8 The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.

HEAP-DELETE(A,i)
temp = A[i]
A[i] = A[A.heapsize]
A.heapsize = A.heapsize -1
if A[i] < temp
MAX-HEAPIFY(A,i);
else
MAX-HEAP-INCREASE-KEY(A,i,A[i]);

We need to see if the new is greater than or less than the old element. Because we have it accordingly if we smaller or larger than older number.We may it up the tree if the number larger than old or down the tree if it smaller.