Heap Delete

Lets see how can we delete a key present at root from a max heap.The root key is replaced by last key (as heap should always be complete) and then this last key is shifted down accordingly to satisfy the max heap property.

Algorithm

1. current loc = 1.last element = arr[n].

2. while child exists
   a. calcualte loc of left child and right child

   b.if last element > children
        break 
     else
        if left child key > right child key
           copy left child key into current loc
           make left child loc as current loc
        else
           copy right child key into current loc
           make right child loc as current loc
3.Copy last element to current loc.

4.Decrement no of elements by 1.

Code

int del(int n)                                      //delete root element
{
    int curr_loc=1,last_el = arr[n],lchild_loc,rchild_loc;

    while(2*curr_loc<=n)                            //child exists
    {
        lchild_loc = 2*curr_loc;
        rchild_loc = lchild_loc+1;

        if(last_el > arr[lchild_loc] && last_el > arr[rchild_loc])
            break;
        else                                       //which child is greater
        {
            if(arr[lchild_loc]> arr[rchild_loc])
            {
                arr[curr_loc] = arr[lchild_loc];
                curr_loc = lchild_loc;
            }
            else
            {
                arr[curr_loc] = arr[rchild_loc];
                curr_loc = rchild_loc;
            }
        }   
    }   
    arr[curr_loc] = last_el;
    n--;

    return n;
}

Code Tracing

Let        cl = curr_loc                lc =  lchild_loc         rc = rchild_loc