#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 ;
}