用数组表示堆的相关知识

//如何手写一个堆
1.插入一个数
2.求集合中的最小值
3.删除最小值（前3个STL中可直接实现）
4.删除任意一个元素
5.修改任意一个元素
//堆：是一颗完全二叉树（即除了叶子节点之外，其余层节点都是非空的，叶子节点从左到右依次排步）
小根堆性质：每个点都是小于等于左右儿子的
//堆的存储：//全新存储方式
下标为1存储根节点，其余的下标为x节点的左儿子在下标2x处、左儿子在下标2x+1处
//以上5个功能都可以在底层用up和down函数实现
1.插入一个数 heap[++ size] = x; up(size);
2.求集合中的最小值 heap[1];
3.删除最小值 heap[1] = heap[size]; size –; down(1);
4.删除任意一个元素 heap[k] = heap[size]; size –;(heap[k]的值变大就用up(k),变小就用down(k))
或者不用判断直接down();up()
5.修改任意一个元素 heap[k] = x; down(k); up(k);

程序

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, m;
int h[N], size1;

void down(int u)
{
    int t = u;//用t表示某个点及其左右儿子中最小的值
    if (u * 2 <= size1 && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size1 && h[u*2+1] < h[t]) t = u * 2 + 1;
    if(u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

void up(int u)
{
    while(u / 2 > 0 && h[u / 2] > h[u])
    {
        swap(h[u], h[u/2]);
        u /= 2;
    }
}


int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    size1 = n;
    for(int i = n/2; i ;i --) down(i);//堆的建立优化成O(n)

    while(m --)
    {
        printf("%d ",h[1]);//输出当前最小的数
        h[1] = h[size1 --];//删除最小数，进行推排序
        down(1);
    }
    return 0;
}