/*
 堆排序
 */
#include <iostream>
using namespace std;
int *data;
void Sift(int k,int last)
{
    int i,j,temp;
    i=k;j=2*i+1;
    while (j<=last)
    {
        if(j<last&&data[j]<data[j+1]) j++;
        if(data[i]>data[j])
            break;
        else
        {
            temp=data[i];
            data[i]=data[j];
            data[j]=temp;
            i=j;
            j=2*i+1;
        }
    }
}
void HeapSort(int length)
{
    int i,temp;
    for(i=ceil(length/2)-1;i>=0;i--)
    {
        Sift(i, length-1);
    }
    for(i=1;i<length;i++)
    {
        temp=data[0];data[0]=data[length-i];data[length-i]=temp;
        Sift(0, length-i-1);
    }
    for(int j=0;j<length;j++)
    {
        cout<<data[j]<<"\t";
    }
    cout<<endl;
}
int main()
{
    data=new int[10]{1,5,23,76,32,7,21,43,-21,44};
    HeapSort(10);
}