C++ 通用小根堆函数

方俊懿 · 2020-02-17 14:38:51 · 个人记录

类型是Type，要换修改即可。

请确保你的Type类型定义了小于号。

亮Code

#define Type int

void siftup(Type h[],int i,int n)
{
    int f=0;
    while(f==0 && i>1 && i<=n)
    {
        if(h[i]<h[i/2])
        {
            Type t=h[i];
            h[i]=h[i/2];
            h[i/2]=t;
        }
        else
            f=1;
        i/=2;
    }
}
void siftdown(Type h[],int i,int n)
{
    int f=0,t=i;
    while(f==0 && i*2<=n)
    {
        if(h[i*2]<h[t])
            t=i*2;
        if(i*2+1<=n)
        {
            if(h[i*2+1]<h[t])
                t=i*2+1;
        }
        if(t!=i)
        {
            Type tt=h[i];
            h[i]=h[t];
            h[t]=tt;
        }
        else
            f=1;
        i=t;
    }
}
void push(Type h[],Type add_,int *n)
{
    h[++(*n)]=add_;
    siftup(h,*n,*n);
}
void pop(Type h[],int *n)
{
    h[1]=h[(*n)--];
    siftdown(h,1,*n);
}
Type top(Type h[])
{
    return h[1];
}