#include<iostream>
using namespace std;

void HeapAdjust(int arry[], int i, int size)  //大小为size的数组arry，将其中以位置i为根节点的子树转换为小根堆 
{
	
	for(int j=2*i+1; j<size; j=j*2+1) //将i结点的数据与其左右孩子比较，若其小于左右孩子，则与左右孩子中的较小值交换
	{   
	    int x = arry[i];
		if(j+1<size&&(x>arry[j]||x>arry[j+1]))  //若右孩子存在 
		{
			if(arry[j]<=arry[j+1])
			{
				arry[i] = arry[j];
				arry[j] = x;
			}
			else
			{
				arry[i] = arry[j+1];
				arry[j+1] = x;
				j++;
			}
			i = j;  
		}
		else if(j+1==size&&x>arry[j])  //若右孩子不存在 
		{
			arry[i] = arry[j];
			arry[j] = x;
			i = j;  //交换后继续将以结点i为根节点的子树转换为小根堆
		} 
		else
		{
			break;
		}
	}
}

void HeapSort(int arry[], int size)  //堆排序 
{
	for(int i=size/2-1; i>=0; --i)  //对所有非叶子结点进行小根堆化，使得整个数组成为一个小根堆 
	{
		HeapAdjust(arry,i,size);
	}
	
	for(int i=size-1; i>0; --i)
	{
		int t = arry[0];  //将新构造的小根堆的根交换到数组的末尾， 
		arry[0] = arry[i];
		arry[i] = t;
		
		HeapAdjust(arry,0,i); //用数组的前i个数据继续构造新的小根堆 
	}
}

int main()
{
	int a[] = {81,94,11,96,12,35,17,95,28,58,41,75,15};
	HeapSort(a,13);
	for(int i=0; i<13; ++i)
	{
		cout << a[i] << " ";
	}
}