#include  < iostream >
#include  < algorithm >
using namespace std;

const   int  MAXN  =   10000 ;

class MinHeap {
public :
    MinHeap();
    MinHeap( int   * ,  int );
    void swim( int );
    void sink( int );
    void insert( int );
    void build();
    void decreaseKey( int  ,  int );
     int  delMin();
     int  getMin();
    void heapSort( int   * ,  int );
private :
     int  a[MAXN];
     int  hSize;
     int   * arr;
};

MinHeap::MinHeap() {
    hSize  =   0 ;
}

MinHeap::MinHeap( int   * b,  int  bLen) {
    hSize  =  bLen;
    arr  =  b;
     for  ( int  i = 0 ; i < bLen; i ++ ) a[i + 1 ]  =  b[i];
    build();
}

void MinHeap::swim( int  p) {
     int  q  =  p  >>   1 , t  =  a[p];
     while  (q ! =   0 ) {
         if  (t  >=  a[q]) break;
        a[p]  =  a[p];
        p  =  q;
        q  =  p  >>   1 ;
    }
    a[p]  =  t;
}

void MinHeap::sink( int  p) {
     int  q  =  p  <<   1 , t  =  a[p];
     while  (q  <=  hSize) {
         if  (q  <  hSize  &&  a[q]  >  a[q + 1 ]) q ++ ;
         if  (a[q]  >=  t) break;
        a[p]  =  a[q];
        p  =  q;
        q  =  p  <<   1 ;
    }
    a[p]  =  t;
}

int  MinHeap::delMin() {
     int  ret  =  a[ 1 ];
    a[ 1 ]  =  a[hSize -- ];
    sink( 1 );
    return ret;
}

void MinHeap::insert( int  key) {
    a[hSize ++ ]  =  key;
    swim(hSize);
}

void MinHeap::decreaseKey( int  p,  int  t) {
    a[p]  =  t;
    swim(p);
}

void MinHeap::build() {
     for  ( int  i = hSize / 2 ; i > 0 ; i -- ) sink(i);
}

int  MinHeap::getMin() {
    return a[ 1 ];
}

void MinHeap::heapSort( int   * b,  int  bLen) {
    hSize  =  bLen;
     for  ( int  i = 0 ; i < bLen; i ++ ) a[i + 1 ]  =  b[i];
    build();
     int  i, k  =   0 ;
     while  (hSize  >   0 ) {
        b[k ++ ]  =  a[ 1 ];
        a[ 1 ]  =  a[hSize -- ];
        sink( 1 );
    }
     for  (i = 0 ; i < bLen; i ++ ) cout  <<  b[i]  <<   '  ';
}

int  main() {
     int  b[]  =  { 5 ,  4 ,  3 ,  2 ,  1 ,  2 ,  9 ,  8 ,  7 };
    MinHeap h;
    h.heapSort(b, sizeof(b) / sizeof(b[ 0 ]));
    system( " pause " );
    return  0 ;
}