堆排序（手写优先队列）

堆--->完全二叉树

小根堆：每个点均小于等于左右两个儿子。

如何手写一个堆？

1，插入一个数；heap[++size]=x;up(size);

2，求集合当中最小值；heap[1];

3，删除最小值；heap[1]=heap[size--];down(1);

4，删除任意一个元素；heap[k]=heap[size--];down(k);up(k);

5，修改任意一个元素；heap[k]=x;down(k);up(k);

注：

为什么从n/2开始down（i）？

因为n/2是最后一个叶子结点的双亲，依次向根结点排序，使其满足小根堆的定义。 

在void down函数里，先让双亲跟左儿子比较，如果左儿子比双亲小，那么将双亲跟左儿子交换数值，再将左儿子跟右儿子比较大小，同前一个比较。

最后如果在孩子中找到最小的那个数值以后，跟双亲交换数值，最后用顺着向下递归

代码：

#include 
using namespace std;
const int N = 100010;
int heap[N], flag, n, k;
void down(int u)
{
    int t = u;
    if (u * 2 <= flag && heap[u * 2] < heap[t])t = 2 * u;
    if (u * 2 + 1 <= flag && heap[u * 2 + 1] < heap[t])t = 2 * u + 1;
    if (u != t)
    {
        swap(heap[u], heap[t]);
        down(t);
    }
    return;
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i < =n; i++)cin >> heap[i];
    flag = n;

    for (int i = n / 2; i; i--)
        down(i);

    while (k--)
    {
        cout << heap[1] << ' ';
        heap[1] = heap[flag--];
        down(1);
    }
    return 0;
}