ACM模板——堆操作集合

/* 以下为 min heap 为例 */#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=1e4+10;
inta[maxn], b[maxn], len, k;
voidshift_up(inti)
{
while((i>>1)>=1)
    {
if(a[i]<a[i>>1]) swap(a[i],a[i>>1]);
elsereturn;
i>>=1;
    }
}
voidshift_down(inti)
{
intt;
while((i<<1)<=len)
    {
t=i<<1;
if(t<len&&a[t]>a[t+1]) t++;
if(a[t]<a[i]) swap(a[t],a[i]);
elsereturn;
i=t;
    }
}
voidheap_push(intnum)
{
a[++len]=num;
shift_up(len);
}
voidheap_build()
{
inti, f, l, r, p, cid;
while(1)
    {
f=0, i=len;
while((i>>1)>=1)
        {
p=i>>1, l=p<<1, cid=l;
if(l+1<=len)
            {
r=l+1;
if(a[r]<a[l]) cid=r;
            }
if(a[cid]<a[p]) f=1, swap(a[cid],a[p]);
i=(p-1)<<1;
        }
if(!f) return;
    }
}
voidheap_pop()
{
swap(a[1],a[len]);
len--;
shift_down(1);
}
intheap_top()
{
returnlen==0?-INF : a[1];
}
boolheap_empty()
{
return!len;
}
voidheap_sort()
{
k=0;
while(len>0)
    {
b[k++]=heap_top();
heap_pop();
    }
}
intmain()
{
intn,num;
scanf("%d",&n);
for(inti=1;i<=n;i++) scanf("%d",&num), heap_push(num); // 边插边建for(inti=1;i<=len;i++) printf("%d ",a[i]); puts("");
for(inti=1;i<=n;i++) scanf("%d",&a[++len]);
heap_build();                                           // 插完再建for(inti=1;i<=len;i++) printf("%d ",a[i]); puts("");
heap_sort();
for(inti=0;i<k;i++) printf("%d ",b[i]); puts("");
return0;
}

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
vector<int>v, v1;
intmain()
{
intn,a;
scanf("%d",&n);
// 边插边建for(inti=1;i<=n;i++) scanf("%d",&a), v.push_back(a), make_heap(v.begin(),v.end(),greater<int>()); // make_heap or push_heapfor(inti=0;i<v.size();i++) printf("%d ",v[i]); puts("");
// 插完再建for(inti=1;i<=n;i++) scanf("%d",&a), v1.push_back(a);
make_heap(v1.begin(),v1.end(),greater<int>());
for(inti=0;i<v1.size();i++) printf("%d ",v1[i]); puts("");
// 先将待插入的元素插入到底层容器的末端，通过 push_back 函数实现。// 再调用 push_heap(b,e,cmp) 函数堆新插入的元素做向上调整。for(inti=1;i<=n;i++) scanf("%d",&a), v.push_back(a);
push_heap(v.begin(),v.end(),greater<int>());
for(inti=0;i<v.size();i++) printf("%d ",v[i]); puts("");
// 先调用pop_heap函数将首部的元素与尾部元素交换，再将原尾部的元素做向下调整操作。此时，原堆顶元素被放置在最后一个位置，并未从底层容器中删除。// 若要实现真正的元素删除，可以调用底层容器的pop_back函数。for(inti=1;i<=n;i++) scanf("%d",&a), v.push_back(a);
pop_heap(v.begin(),v.end(),greater<int>());
v.pop_back();
for(inti=0;i<v.size();i++) printf("%d ",v[i]); puts("");
return0;
}