[数据结构与算法]堆（模板）

堆排序

#include<iostream> 
#include<algorithm>

using namespace std;

const int N = 100010;

int h[N], mySize;

int n, m;

void down(int u)
{
    int t = u;
    if (2 * u <= mySize && h[t] > h[2 * u])       //down节点u--u的左儿子2*u--右儿子2*u+1,u节点值>左儿子值,t=左儿子的下标 
        t = 2 * u;
    if (2 * u + 1 <= mySize && h[t] > h[2 * u + 1])//u节点值>右儿子值,t=右儿子的下标
        t = 2 * u + 1;  
    if (u != t)                                   //最小值不是u时,t!=u,交换u,t的值                       
    {
        swap(h[u], h[t]);
        down(t);                                  //递归t
    }
}

int main()
{
    cin >> n >> m;
    mySize = n;                                //传递时使用mySize,因为节点数量在变化,而n却没有变化
    
    for (int i = 1; i <= n; i++)scanf("%d", &h[i]);
        
        
    for (int i = n / 2; i; i--)down(i);        //遍历一半的点即可,形成小根堆

    while (m--)                                //输出前m小的数
    {
        cout << h[1] << " ";
        h[1] = h[mySize],mySize--, down(1);    //使得h[1]=最后一个数,节点数量减小,h[1]较大-进行down(1)
    }
    
    return 0;
}

2.模拟堆

//题意：即使节点删除,down(),up(),但是第K次插入的节点和堆中节点下标是不随着节点的移动而变化的
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
int h[N];   //堆,从下标1开始
int ph[N];  //存放第k个插入点的下标ph[k]=u 
int hp[N];  //存放堆中点的插入次序hp[u]=k
int mysize; //记录的是堆当前的数据多少

//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响

void heap_swap(int u,int v)
{   
    swap(h[u],h[v]); 
    swap(hp[u],hp[v]);     
    swap(ph[hp[u]],ph[hp[v]]);            

}

void down(int u)
{
    int t=u;
    if(u*2<=mysize&&h[t]>h[u*2]) t=u*2;
    if(u*2+1<=mysize&&h[t]>h[u*2+1])  t=u*2+1;
    if(u!=t)
    {
        heap_swap(u,t);
        down(t);
    }
}

void up(int u)
{
    if(u/2>0&&h[u]<h[u/2]) 
    {
        heap_swap(u,u/2);
        up(u>>1);
    }
}

int main()
{
    int n;
    cin>>n;
    int m=0;    //m用来记录插入的数的个数
                //注意m的意义与mysize是不同的 mysize是记录堆中当前数据的多少
                //对应上文 m即是hp中应该存的值
    while(n--)
    {
        string op;
        int k,x;
        cin>>op;
        if(op=="I")
        {
            cin>>x;
            m++;
            h[++mysize]=x;
            ph[m]=mysize;
            hp[mysize]=m;
            up(mysize);
        }
        else if(op=="PM")    cout<<h[1]<<endl;
        else if(op=="DM")
        {
            heap_swap(1,mysize);
            mysize--;
            down(1);
        }
        else if(op=="D")
        {
            cin>>k;
            int u=ph[k];                   //这里一定要用u=ph[k]保存第k个插入点的下标
            heap_swap(u,mysize);          //因为在此处heap_swap操作后ph[k]的值已经发生 
            mysize--;                    //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            up(u);
            down(u);
        }
        else if(op=="C")
        {
            cin>>k>>x;
            h[ph[k]]=x;                 //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个
            down(ph[k]);                //所以可直接传入ph[k]作为参数
            up(ph[k]);
        }

    }
    return 0;
}