堆排序

1、堆排序（Heap Sort）：要求堆中的节点的值都大于或等于其孩子节点的值。

---- 对简单选择排序进行的一种改进。

---- 堆是具有下列性质的完全二叉树：

---- 大顶堆：每个结点的值都大于或等于其左右孩子结点的值。

---- 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

---- 堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是：

将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与大顶堆的末尾元素交换，此时末尾元素

就是最大值），然后将剩余的n-1个序列重新构造成一个大顶堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

2、建堆 -- 插入一个元素 -- 删除一个元素

--1）建堆：数组具有对应的树表示形式。一般情况下，树并不满足堆的条件。通过重新排列元素，可以建立一棵“堆化”的树。

初始化：10  40  30

--2）插入一个元素：新元素被加入到表中，随后树被更新以恢复堆次序。例如，下面的步骤将15加入到表中。

15加入                                                                                                重排树的顺序

--3）删除一个元素：删除总是发生在根节点处。用表中的最后一个元素来填补空缺位置，最后树被更新以恢复堆条件。

排序后的删除根节点                                          用最后一个元素10来填补根节点元素                重新排序后

3、算法实现

#define MaxSize 10	//要排序数组元素的最大值，可根据需要修改
typedef struct 
{
	int r[MaxSize+1];//用于存储要排序数组，r[0]用作哨兵或临时变量
	int length;	//用于记录顺序表的长度
}SqList;

void swap(SqList *L,int i,int j)
{
	int t = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = t;
}
/*Heap Sort,将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。
将它移走（就是将其与堆的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列
重新构造成一个堆，得到n个元素中的次小值。如此反复进行，便能得到一个有序序列了。
*/
//已知L->r[s...m]中记录的关键字除L->r[s]之外均满足堆的定义
//本函数调整L->r[s]的关键字，使L->[s...m]称为一个大顶堆。
void HeapAdjust(SqList *L,int s,int m)
{
	int temp,i;
	temp = L->r[s];
	for(i=2*s;i<=m;i*=2)
	{
		if(ir[i]r[i+1])
			++i;
		if(temp>=L->r[i]) //根结点大于等于孩子结点中较大的那一个，跳出循环，整个堆符合大顶堆的结构。
			break;
		L->r[s] = L->r[i];//将较大孩子结点的值赋给根结点
		s = i;
	}
	L->r[s] = temp; //找到位置，插入
}
void HeapSort(SqList *L)
{
	int i;
	for(i=L->length/2;i>0;i--)
	{
		HeapAdjust(L,i,L->length);//将L中的r构建成一个大顶堆
	}
	for(i=L->length;i>1;i--)
	{
		swap(L,1,i);//将堆顶记录和最后一个记录交换
		HeapAdjust(L,1,i-1); //将L->r[1...i-1]重新调整为大顶堆
	}
}
int main()
{
	SqList *L = (SqList*)malloc(sizeof(SqList));
	int a[MaxSize] = {9,1,5,8,3,7,4,6,2,0};
	for(int i=0;ir[i+1] = a[i];
	}
	L->length = MaxSize;
	HeapSort(L);
	cout<<"排序后的序列如下："<<endl;
	for(int i=1;ilength;i++)
	{
		cout<r[i]<<" ";
	}
	cout<<endl;
	system("pause");
	return 0;
}