堆排序

什么是堆排序呢，这里大概讲讲……

我们在这里讲到的堆，一般是二叉堆，也就是完全二叉树或者近似完全二叉树的一个数据结构。

如果说每个节点的值都大于他的任意子节点的值就叫做大根堆，反之称作小根堆。

我们通常是通过利用一个一维数组来存储一个堆的，如果说起点是从0开始，那么其左子节点就是2i+1，右子节点就是2i+2；  而如果说起点是从1开始的，那么其左子节点就是2i，右子节点是2i+1；

好的，介绍完了堆的基本性质，我们接下来就具体介绍一下怎么实现这个堆排序

基本思想：我们还是通过递归的思想来解决这个问题，我们设计一个down函数以便于对当前这个节点以下的子树全部都正确排序，所以为了实现这个目标，我们还需要进行递归操作。然后为了保证每一棵子树都能被down函数检查过，我们从树的倒数第二层往上遍历，对于遍历到的每一个节点都去down一遍。

分析：1.为什么要递归：避免一个数本该到最下面一层却因为只能down一次，在倒数第二层的地方卡住了，不能很好地维护这个堆；

           2.为什么对于每一个点都要遍历以及为什么只需要倒数第二层以上的点：因为如果不全down一次的话，只down（1）有可能会让二叉树的一边是排好序了，但另一边就不清楚了；     而且对于最下面一层的节点来说，他们没有子节点了，没有down的意义。

上代码：

#include
#define maxn 100010

using namespace std;
int n,m;
int h[maxn],idx;

void down(int u){
int t = u;
if(2*u<= idx && h[2*u]
if(2*u+1<= idx && h[2*u+1]
if(t != u) {
swap(h[t],h[u]);
down(t);
}
}

int main()
{
std::ios::sync_with_stdio(false) ; std::cin.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++) cin>>h[i];
idx = n;
for(int i = n/2; i; i--) down(i);

while(m--){
cout<
h[1] = h[idx];
idx--;
down(1);
}
return 0;
}

分析：这里还应注意的是我们要逐渐输出最小值，所以我们每次都要抛掉根节点，操作是通过交换根节点和当前最大的节点，然后使根节点down下去，总节点数减一；