堆排序

支持的操作
1. 插入一个数
2. 求集合中的最小值
3. 删除最小值
4. 删除任意一个元素
5. 修改任意一个元素

小根堆： 父节点小于等于左右两个子节点的值。

储存方式: x的左儿子是2*x, 右儿子是2 * x + 1, 用一维数组来存储。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int h[N];
int s = 0;
void down(int u)
{
    int t = u;
    if(u * 2 <= s && h[u * 2] < h[t])t = u * 2;
    if(u * 2 + 1 <= s && h[u * 2 + 1] < h[t])t = u * 2 + 1;
    if(u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)cin >> h[i];
    s = n;
    
    for(int i = n / 2; i ; i --)down(i);//除了叶节点都要下沉
    
    while(m --)
    {
        printf("%d ", h[1]);
        
        h[1] = h[s];
        s --;
        down(1);
    }
}

链接