堆排序算法

题目描述
编写程序堆排序算法。按照从小到大的顺序进行排序，测试数据为整数。

输入
第一行是待排序数据元素的个数； 第二行是待排序的数据元素。（提示：用小根堆）

输出
一趟堆排序的结果。

样例输入

10
50 36 41 19 23 4 20 18 12 22

样例输出

4 12 20 18 22 41 50 36 19 23
 

父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）

左孩子索引：2*i+1

右孩子索引：2*i+2

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
大顶堆性质：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
小顶堆性质：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

把数据以顺序二叉树存储结构进行存储，从非叶子结点的最底层（n/2)挨个结点向上开始遍历，左右孩子双亲三个结点中最小的那一个与双亲结点交换值，执行到到根节点即可停止。

#include
#define ll long long
//#define int ll
#define pii pair
#define mem(a,b) memset(a,b,sizeof(a))
#define endl 'n'
#define N 100005
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
using namespace std;
//int a[1005][1005]; 
int a[N],n;
void sift(int i)
{
	int j=i*2;//j为i的左孩子
	int top=a[i];
	while(j<=n)
	{
		if(ja[j+1]) j++;//找到最小的孩子
		if(top>a[j])//如果top的值大于最小孩子的值
		{
			a[i]=a[j];//将最小孩子的值赋值给当前结点
			i=j;//最小孩子变成新的当前结点 
			j=2*i;//继续向下查找top的位置
		}
		else break;		
	} 
	a[i]=top;//找到top位置后赋值 
}
signed main()
{	
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n/2;i>=1;i--)//从非叶子结点的最底层（n/2)挨个结点向上开始遍历
		sift(i);
	for(int i=1;i<=n;i++)
		cout<