止于自娱

static   void  _build_heap( int   * array, int  len);
static   void  _adjust_heap( int   * array, int  idx, int  len);

int  heap_sort( int   * array, int  begin, int  end)
{
     if (array == NULL || begin > end)  return   0 ;

     // 自此以后，index从1开始。
    array -- ;
     int  len  =  end - begin + 1 ;
    _build_heap(array,len);

     int  tmp;
     int  i;

     for (i = 1 ;i < len; ++ i){
        tmp  =  array[len - i + 1 ];
        array[len - i + 1 ]  =  array[ 1 ];
        array[ 1 ]  =  tmp;
        _adjust_heap(array, 1 ,len - i);
    }
}

// input: 任意数组 output:大顶堆
static   void  _build_heap( int   * array, int  len)
{
    int  i;
    for (i = len / 2 ;i >= 1 ; -- i){
        _adjust_heap(array,i,len);
   }
}

// 使重新使array满足堆特性
static   void  _adjust_heap( int   * array, int  idx, int  len)
{
     int  left;
     int  right;
     int  larger  =  idx;
     int  tmp  =  array[idx];

    left  =  (idx << 1 );
    right  =  left + 1 ;

     while ( left <=  len){
         if (right <= len && array[right] > array[left]){
            larger  =  right; 
        } else {
            larger  =  left;
        }

         if ( array[larger] > tmp ){
            array[idx]  =  array[larger];
            idx  =  larger;
            left  =  (idx << 1 );
            right  =  left + 1 ;
        } else {
             break ;
        }
    }

    array[idx]  =  tmp;
}