堆排序

逻辑结构是完全二叉树，其左右孩子结点都小于或者都大于父结点的结构叫做堆，一个叫小顶堆，还有一个叫大顶堆。

我们可以用一个数组来存储完全二叉树

建堆操作

插入结点

删除结点
例如我们想要删除这个根结点，我们可以先将这个结点拿的丢在一边，然后将最后一个结点丢在这个删除的结点的位置，然后对这个堆做一个调整。

堆排序的实现，我们分为两个过程，第一个过程是我们首先要建堆，第二个过程是我们从中挑出一个最值，然后把他丢在末尾，然后对其做一次调整。这两个过程说到底都是对某个关键字进行调整的过程。
所以实现这个堆排序也要两个函数，一个函数是对某个关键字进行调整的函数，还有一个函数是堆排序的主函数。

void sift(int arr[],int low,int high)  //调整函数
{
	int i=low,j=2*i+1;
	int temp=arr[i];
	while(j<=high)
	{
		if(j<high&&arr[j]<arr[j+1])
			++j;
		if(temp<arr[j])
		{
			arr[i]=arr[j];
			i=j;
			j=2*i+1;

		}
		else
			break;
	}
	arr[i]=temp;
}

void heapSort(int arr[],int n)  //主函数
{
	int i;
	int temp;
	for(i=n/2-1;i>=0;--i)
		sift(arr,i,n-1);  //生成了大顶堆
	for(i=n-1;i>0;--i)
	{
		temp=arr[0];
		arr[0]=arr[i];
		arr[i]=temp;
		sift(arr,0,i-1); // 有序序列
	}
}

我们首先走一下这个函数，我们走到主函数中的for（i=n/2-1;i>0;–i)，i=8/2-1=3,然后我们下一句，我们调用调整函数，sift（arr，i,n-1）作用arr数组里的数，范围是i到n-1，即3到7。
我们到调整函数，i=low,然后j=2*i+1，这句是j指向i的左孩子（这个是完全二叉树中找其孩子结点的公式）

我们看第7行的if语句，这句话的意思就是，如果i的左右孩子结点都存在的话，那么就将j指向左右孩子中较大的那个结点。此时这里i=3,他这个结点只有左孩子没有右孩子，不满足这个条件，所以就跳过。第8行的if语句，如果temp所指结点小于arr[j]的话，那就将
j位置的值赋给i位置上，然后让i指向j，j指向i的左孩子结点，如果不满足条件，直接break.执行完这个调整函数之后，我们就恢复现场，此时还在26行的for循环中，再一次循环,–i，之前的i是3，所以这一次循环的i=2，然后再进入调整函数。这样一直循环。

调整函数中两个for循环都是为了生成大顶堆，主函数中的for（i=n-1;i>0;–i）就是生成有序序列。