如何手写一个堆？

堆支持的操作：

1. 插入一个数

2. 求集合当中的最小值

3. 删除最小值

4. 删除任意一个元素

5. 修改任意一个操作

后面两个操作无法直接用STL实现。

堆本质上是一棵完全二叉树。以小根堆为例，其每个点都是小于等于左右子节点的，根节点就是整个树的最小值。

堆的存储方式：用一维数组存储，设根节点的下标是x,则左儿子是2x，右儿子是2x+1.

往下调整与往上调整：
如果某个数变大了，就要把它往下移,直到不能下移为止；反之，则要往上移。

heap[++size] = x;up(size); //插入一个数
heap[1]; //求最小值
heap[1] = heap[size];size--;down(1); //删除最小值
heap[k] = heap[size];size--;down(k);up(k); //删除任意一个元素
heap[k] = x;down(k);up[k]; //修改任意一个元素

题目描述

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式

第一行包含整数n和m。

第二行包含n个整数，表示整数数列。

输出格式

共一行，包含m个整数，表示整数数列中前m小的数。

数据范围

1≤m≤n≤10^5，
1≤数列中元素≤10^9

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

具体实现

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n,m;
int h[N],size;

void down(int u)
{
    int t = u;
    if(u*2 <= size && h[u*2] < h[t]) t = u*2;
    if(u*2 + 1 <= size && 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 && h[u/2] > h[u])
    {
        swap(h[u/2],h[u]);
        u /= 2;
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++) scanf("%d",&h[i]);
    size = n;

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

    while(m--)
    {
        printf("%d ",h[1]);
        h[1] = h[size];
        size--;
        down(1);
    }

    return 0;
}