1.简介

堆排序（英语:Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

2.堆的分类

2.1 大顶堆

父节点的键值总是大于小于子节点的键值，这种堆叫大顶堆（大根堆)。

黑色的数字表示 x[i]，红色的数字表示 i 。这是完全二叉树的算法特点。第 i 号节点是 x[i]，它的左儿子是 x[2*i+1], 右儿子是 x[2*i+2]。

对于大顶堆而言，必须要满足: x[i] >= x[2*i+1] && x[i] >= x[2*i+2]。 x[0] 是全部数据中键值最大的值。

2.2 小顶堆

父节点的键值总是小于等于子节点的键值，这种堆叫小顶堆（也叫小根堆）。

对于小顶堆而言，必须要满足: x[i] <= x[2*i+1] && x[i] <= x[2*i+2]。x[0] 是全部数据中键值最小的值。

3.堆排序的应用场景

这种排序的应用场景是：我们只关心最大值（或者最小值）是什么，至于第二大、第三大、第四大.....我们不关心。持续维护大顶堆、小顶堆的开销不是很大，所以要计算的数据是不断变化，又不断的要求出某个时间的最大值、最小值，那么用堆排序就比较高效。

4.算法步骤

1. 首先把数组构看成是一刻二叉树，对于任意一个 x[i]，左儿子是 x[2*i+1]，右儿子是左儿子是 x[2*i+2] ，根节点是 x[0]。（如果根节点是 x[1], 则左儿子是 x[2*i]，右儿子是左儿子是 x[2*i+1]）

2. 对数据做第一次排序。类似冒泡算法那样，把大的数据网上冒。

3. 如果要取出最大的数据，则取出 x[0] (取出之后，一般都要删掉的），把 x[n-1] 放置到 x[0]，然后基于递归的思想，调换位置，一直到某一层不需要换位置（符合堆的特点），就结束。

4. 如果是插入一个新的数据，则放置到 x[n++]，然后自下而上做挪动，知道某一层需要换位置（符合堆的特点），就结束。

所以，用堆排序的场景往往就是数据不断的变化，然后总是围绕着最大值最小值做文章，然后你的程序则一直维护这二叉树的结构。

5.算法模板

堆排序往往不是面向静态数据场景的，如果是静态的数据，往往有别的排序方法会更加胜任。

所以，堆排序的算法细节分成了几个部分：

1. push_up

把二叉树分解成很多个最简子结构，每个最简子结构都有父亲和儿子，如果是叶子节点，则没有儿子。对于完满二叉树来说，最后一个叶子节点是 x[n]，它的父亲是 x[n/2]。

对于一个最简子结构来说，如果儿子比自己的父亲大，那么儿子就要和父亲做交换了位置了。push_down 是一个递归的过程（或者是循环的过程），如果儿子和父亲交换了，那么就继续往下看看，看发生了数据交换的那个儿子的子树，继续 push_down。

2. 初次排序

初次排序就是要把一个无序的数组（堆），排序成一个大顶堆或者小顶堆。如果是程序题，用 sort 函数来完成初次排序是可以的，一个严格有序的序列，一定也是有序堆，从小到大排序的数组是小顶堆，从大到小排序的数组是大顶堆。

但是，理论知识一定要知道，如果要自己写一个堆排序的程序，不依赖于 STL （sort 函数也是 STL 的一部分），怎么写？

节点数为 n 的堆，第一个有孩子的节点是 n/2（n/2 之后的节点都是叶子节点，叶子节点没有儿子）。所以最开始从 u=n/2 开始 push_down 。在持续的 push_down 中，先 push_down 下方的节点，而且 push_down 是递归的，所以，push_down(u) 之后，u 的整棵子树都是符合堆排序的。又因为子树已经有序，所以，push_down 的过程中如果在某个子结构中符合父亲比儿子大（大顶堆），那么就不需要继续往下 push_down 了。

按照这个方式，从 u/2 到 1 都 push_down 完，整个堆都有序了。

3. pop

x[1] 就是堆顶。当 x[1] 弹出之后，可以把 x[n] 挪动到 x[1] （然后 n--）。这时候这棵树是除了 x[1] 都是符合堆的顺序特性，所以，只需要从 x[1] 开始往下 push_down 即可。假设这棵树的规模是 n，那么树的最大深度就是 $log_2^n$ ，每一次 pop 之后，从 x[1] 做push_down，计算福大度是 $log_2^n$ ，如果 n = 100000，那么最坏的情况就是做了 17 次比较和交换。

4. push_up

假设是往堆里新增一个元素，我们可以把这个数放在 x[n+1] ，这个堆除了 x[n+1] 之外，其余位置都是符合堆的顺序特性的，所以，只需要从 x[(n+1)/2] 做一次 push_up 即可。

push_up 和 pu_down 类似，不同之处是当发生交换的时候，往上做递归的 push_up

#include<bits/stdc++.h>
using namespace std;
int x[1001],n;
void push_down(int p) //检查 x[p], x[p*2], x[p*2+1] 
{
	int LC = p*2; // 左儿子 
	int RC = p*2+1;// 右儿子
	if(RC<=n&&x[LC]<=x[RC]&&x[p]<x[RC]){ //有右儿子，右儿子比父亲和比左儿子都大 
		swap(x[p],x[RC]);
		push_down(RC); // 父亲和右儿子交换，继续从右儿子做 push_down
	}
	else if(LC<=n&&x[p]<x[LC]){ //有左儿子，左儿子比父亲大 
		swap(x[p],x[RC]);
		push_down(LC);
	}
	// 如果上面 2 个情况都不是，那就不需要交换，这个最简子结构有序
	// 子树在之前的 push_down 中已经保证了有序，所以不需要往下看了 
}
void push_up(int p) //检查 x[p], x[p*2], x[p*2+1] 
{
	int LC = p*2; // 左儿子 
	int RC = p*2+1;// 右儿子
	if(RC<=n&&x[LC]<=x[RC]&&x[p]<x[RC]){ //有右儿子，右儿子比父亲和比左儿子都大 
		swap(x[p],x[RC]);
		if(p/2) push_up(p/2); // 父亲和右儿子交换，继续从父亲做 push_up
	}
	else if(LC<=n&&x[p]<x[LC]){ //有左儿子，左儿子比父亲大 
		swap(x[p],x[RC]);
		if(p/2) push_up(p/2); // 父亲和左儿子交换，继续从父亲做 push_up
	}

}
int insert(int a){
	x[++n] = a;
	push_up(n/2); // 整棵树的其它部分都是有序的，从 n/2 开始检查 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>x[i];

	for(int i=n/2;i>=1;i--)	push_down(i);
	
	//初次输出堆内的根元素（最大的那个），然后把这个跟元素删掉，重新排序，一直到整个数组为空 
	while(n)
	{
		printf("%d\n",x[1]);
		x[1] = x[n--];
		heap_sort(1);
	}

	return 0;
}