[Algorithm] Heap Sort

1. Heap Sort

int push(int n) {
   S[ HI++ ] = n;
   for( int k = HI - 1; k > 1; k /= 2 ) {
      if( S[ k/2 ] <= S[ k ] ) break;
      int temp = S[ k/2 ]; S[ k/2 ] = S[ k ]; S[ k ] = temp;
   }
}

int pop() {
   int v = S[ 1 ];
   S[ 1 ] = S[ --HI ];
   for( int k = 1; k*2 < HI; ) {
      int n = k*2;
      if( HI >= k*2 + 1 ) { n = S[ k*2 ] <= S[ k*2 + 1 ] ? k*2 : k*2 + 1; }
      if( S[ k ] <= S[ n ] ) break; 
      int temp = S[ n ]; S[ n ] = S[ k ]; S[ k ] = temp;
      k = n;
   }
   return v;
}

void heap_sort(int bb, int ee) {
   for( int i = bb; i <= ee; i++ ) push( A[ i ] );
   dump_heap();
   for( int i = bb; i <= ee; i++ ) A[ i ] = pop();
}