// heapsort.java 

public class heapsort
{
  int countintr = 0;
  int countcmp = 0;

  public heapsort()
  {
  }

  public void sortd(double base[], int nmemb)
  {
    int last_parent_pos = ( nmemb - 2 ) / 2;     
    int last_parent_index = last_parent_pos;
    int index_val;
    double item_temp;

    // heapsort main code
    if(nmemb <= 1) return;

    for(index_val=last_parent_index; index_val>=0;index_val--)
      remake_heapd(base, index_val, nmemb-1);
    countintr++;
    // memcpy(item_temp,base,size); 
    // memcpy(base,&base[(nmemb-1)*size],size);
    // memcpy(&base[(nmemb-1)*size],item_temp,size);
    item_temp = base[0];
    base[0] = base[nmemb-1];
    base[nmemb-1] = item_temp;

    for(index_val=nmemb-2; index_val>0; index_val--)
    {
      remake_heapd(base, 0, index_val);
      countintr++;
      // memcpy(item_temp,base,size); 
      // memcpy(base,&base[index_val*size],size);
      // memcpy(&base[index_val*size],item_temp,size);
      item_temp = base[0];
      base[0] = base[index_val];
      base[index_val] = item_temp;
    }
  } // end sortd 

  void remake_heapd(double base[], int parent_index ,int last_index)
  {
    int last_parent_pos = ( last_index - 1 ) / 2;     
    int last_parent_index = last_parent_pos;
    int l_child;
    int r_child;
    int max_child_index;
    int parent_temp = parent_index;
    double item_temp;

    for(;;)
    {
      if(parent_temp > last_parent_index) break;
      l_child = parent_temp * 2 + 1;
      if(l_child == last_index)
      {
        max_child_index = l_child;
      }
      else
      {
        r_child = l_child+1;
        countcmp++;
        if(base[l_child] > base[r_child])
        {
          max_child_index = l_child;
        }
        else
        {
          max_child_index = r_child;
        }
      }
      countcmp++;
      if(base[max_child_index] > base[parent_temp])
      {
        countintr++;
        // memcpy(item_temp,&base[max_child_index*size],size); 
        // memcpy(&base[max_child_index*size],&base[parent_temp*size]
        //        ,size);
        // memcpy(&base[parent_temp*size],item_temp,size);
        item_temp = base[max_child_index];
        base[max_child_index] = base[parent_temp];
        base[parent_temp] = item_temp;
        parent_temp = max_child_index;
      }
      else
      {
        break;
      }
    }
  } // end remake_heapd 

  public void sortdindex(final double base[], int nmemb, int index[])
  {
    int last_parent_pos = ( nmemb - 2 ) / 2;     
    int last_parent_index = last_parent_pos;
    int index_val;
    double item_temp;
    int ix_temp;

    // heapsort main code
    for(int i=0; i<nmemb; i++) index[i] = i; /* indexes get sorted */ 
    if(nmemb <= 1) return;

    for(index_val=last_parent_index; index_val>=0;index_val--)
	remake_heapix(base, index_val, nmemb-1, index);
    countintr++;
    // memcpy(item_temp,base,size); 
    // memcpy(base,&base[(nmemb-1)*size],size);
    // memcpy(&base[(nmemb-1)*size],item_temp,size);
    ///item_temp = base[0];
    ///base[0] = base[nmemb-1];
    ///base[nmemb-1] = item_temp;
    ix_temp = index[0];
    index[0] = index[nmemb-1];
    index[nmemb-1] = ix_temp;

    for(index_val=nmemb-2; index_val>0; index_val--)
    {
      remake_heapix(base, 0, index_val, index);
      countintr++;
      // memcpy(item_temp,base,size); 
      // memcpy(base,&base[index_val*size],size);
      // memcpy(&base[index_val*size],item_temp,size);
      ///item_temp = base[0];
      ///base[0] = base[index_val];
      ///base[index_val] = item_temp;
      ix_temp = index[0];
      index[0] = index[index_val];
      index[index_val] = ix_temp;
    }
  } // end sortdindex

  void remake_heapix(final double base[], int parent_index ,int last_index,
                     int index[])
  {
    int last_parent_pos = ( last_index - 1 ) / 2;     
    int last_parent_index = last_parent_pos;
    int l_child;
    int r_child;
    int max_child_index;
    int parent_temp = parent_index;
    int ix_temp;
    double item_temp;

    for(;;)
    {
      if(parent_temp > last_parent_index) break;
      l_child = parent_temp * 2 + 1;
      if(l_child == last_index)
      {
        max_child_index = l_child;
      }
      else
      {
        r_child = l_child+1;
        countcmp++;
        if(base[index[l_child]] > base[index[r_child]])
        {
          max_child_index = l_child;
        }
        else
        {
          max_child_index = r_child;
        }
      }
      countcmp++;
      if(base[index[max_child_index]] > base[index[parent_temp]])
      {
        countintr++;
        // memcpy(item_temp,&base[max_child_index*size],size); 
        // memcpy(&base[max_child_index*size],&base[parent_temp*size]
        //        ,size);
        // memcpy(&base[parent_temp*size],item_temp,size);
        ///item_temp = base[max_child_index];
        ///base[max_child_index] = base[parent_temp];
        ///base[parent_temp] = item_temp;
        ix_temp = index[max_child_index];
        index[max_child_index] = index[parent_temp];
        index[parent_temp] = ix_temp;
        parent_temp = max_child_index;
      }
      else
      {
        break;
      }
    }
  } // end remake_heapix 

} // end class heapsort