Answer to Question heapsort-1

  //===========================================
  //              reheapUpMax
  //===========================================
  // reheapUpMax(i,A) does a reheapUp operation on
  // the max-heap represented by array A,
  // starting at index i.
  //===========================================

  void reheapUpMax(int i, int A[])
  {
    int j = i;
    while(j > 0)
    {
      int p = parent(j);
      if(A[p] < A[j])
      {
        swap(A[p], A[j]);
        j = p;
      }
      else
      {
        break;
      }
    }
  }

  //===================================================
  //                  reheapDownMax
  //===================================================
  // reheapDown(i, A, n) does a reheapDown operation on
  // the max-heap represented by array A, starting at
  // index i.  Parameter n is the number of values
  // currently in the heap.
  //===================================================

  void reheapDownMax(int i, int A[], int n)
  {
    int p = A[i];
    int j = i;
    while(leftchild(j) < n)  // j is not a leaf
    {
      int lc    = leftchild(j);
      int rc    = rightchild(j);
      int pleft = A[lc];

      if(rc < n)  // j has two children
      {
        int pright = A[rc];
        int m      = max(p, max(pleft, pright));
        if(m == p)
        {
          break;
        }
        else if(m == pleft)
        {
          swap(A[j], A[lc]);
          j = lc;
        }
        else
        {
          swap(A[j], A[rc]);
          j = rc;
        }
      }
      else  // j has only a left child.
      {
        if(p < pleft)
        {
          swap(A[j], A[lc]);
        }
        break;
      }
    }
  }