$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

如何手写一个堆？

• 插入一个数 h[++n]=x; up(n);
• 求集合当中的最小值 h[1];
• 删除最小值 h[1]=h[n--]; down(1);
• 删除任意一个元素 h[k]=h[n--]; down(k); up(k);
• 修改任意一个元素 h[k]=x; down(k); up(k);

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int n,m;
int h[N];

//小根堆，使大的数往下移
void down(int u)
{
    int t=u;
    if(u*2<=n&&h[u*2]<=h[t]) t=u*2;
    if(u*2+1<=n&&h[u*2+1]<=h[t]) t=u*2+1;
    if(u!=t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>h[i];

    //从倒数第二层开始down
    for(int i=n/2;i;i--) down(i);

    //输出最小值，再删除最小值
    while(m--)
    {
        cout<<h[1]<<' ';
        h[1]=h[n--];
        down(1);
    }

    return 0;
}