Heap Insert

For a heap with n elements we have to insert a key (say x) at (n+1)th location.Here we will insert a key in max heap.

Algorithm

Initialize n = 0.

1.Ask key from user.

2.Set current loc to n+1.

3.if n!=0 (not the first element)

     Until current loc>1 (i.e parent exists for current loc)

          a.Find parent loc (= current loc/2)

          b.If key < key at parent location goto 4.

          c.else (key > key at parent loc)

                   Copy key from parent loc to current loc

                   Make parent loc as current loc.

4.Insert key at current loc.Increment n (no of elements) by 1.

5.If user wants to insert more keys goto 1.

Code

int insert(int n)
{
  int par_loc,curr_loc,key;
  char ch;
  do
  {
      printf("Enter key ");
      scanf("%d",&key);

      curr_loc = n+1;

    if(n!=0)
    {
        while(curr_loc>1)
        {
            par_loc = curr_loc/2;

            if(key<arr[par_loc])
                break;

            arr[curr_loc] = arr[par_loc];       //copy key from par_loc to curr_loc
            curr_loc = par_loc;                //make par_loc as curr_loc
        }
    }                           
    arr[curr_loc] = key;
    n++;

    printf("Do u want to insert more nodes ? ");
    fflush(stdin);
    scanf("%c",&ch);

  }while(ch=='y');

return n;
}

Code Tracing