typedef int Datatype;
typedef struct 
{
	Datatype* elem; 
	int Length;
}SqList;
typedef SqList HeapType;
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
//建大堆
//m: 结点个数 s: 待下调父结点下标
void HeapAdjust(HeapType H, int s, int m) 
{
    int child = s * 2;
    while(child <= m)
    {												
        if (child + 1 <= m && H.elem[child] < H.elem[child + 1])
            ++child;		
        if (H.elem[s] < H.elem[child])
        {
            swap(&H.elem[child], &H.elem[s]);

            s = child;
            child = s * 2;
        }
        else
            break;
    }                			
}
// int parent = (child - 1) / 2   // int parent = child / 2  
// int child = parent * 2 + 1;    // int child = parent * 2 ;

void HeapSort(HeapType H)
{ 
    //下调建堆
    for (int i = H.Length / 2; i >= 1; i--)
    {
        HeapAdjust(H, i, H.Length);
    }

    //排序: 依次把堆顶放到表尾
    for (int end = H.Length; end >= 2; end--)
    {
        swap(&H.elem[1], &H.elem[end]);
        HeapAdjust(H, 1, end - 1);
    }
}
int main()
{
    HeapType L;
    //CreatSqList(&L);
    HeapSort(L);
    for (int i = 1; i <= L.Length; i++)
    {
        printf("%d ", L.elem[i]);
    }
    return 0;
}