Cormen Edition 3 Exercise 6.5 Question 8 (Page No. 166)

Question

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.

Answer 1

Heap_Delete(A,i)

{

A[i] = A[A.heapsize]

A.heapsize--

Max_heapify(A,i)

}