操作种类
- 对给定的数组在时间内建堆
- 对已有的堆支持插入,删除,查找操作
实现
建堆操作
根据规律,含有n个元素的完全二叉树为叶子。根据序号从大到小枚举所有非叶子节点,每次迭代的节点均为合法堆的根的父亲节点,(叶节点本身就是一个合法的堆,从大到小枚举保证了上述性质)只需要从该节点向下递归维护合法堆的性质(称为fix)。
插入操作
将插入的元素放在新添加的叶子处,不断和父亲节点比较大小并交换。
删除操作
本来想直接删除根节点,不断从两个儿子节点中找更小的那个上移,但后来发现这样会让编号错乱,导致未pop的元素被后来的元素覆盖,算法导论提供的思路是把a[1]和a[n]调换,n自减1,再对a[1]实行fix。
其他
以后定义宏的时候要小心,注意< >的使用,比如#define ls p>>1
,引用ls的时候最好加个括号,防止编译器误判。
手写堆比STL里的priority_queue快得多。仅有六分之一的时间花费
代码
#include<bits/stdc++.h>
#define rep(i,st,ed) for(int i=st;i<=ed;++i)
#define ls p<<1
#define rs p<<1|1
const int N=1E6+10;
using namespace std;
const int INF=-0x3f3f3f3f;
int n,m,op;
int a[N];
inline int read()
{
int ret=0;char ch=getchar();
while(ch<'0' || ch>'9')
ch=getchar();
while(ch>='0' && ch<='9')
{
ret=ret*10+ch-'0';
ch=getchar();
}
return ret;
}
void fix(int p)
{
int tar=p;
if((ls)<=n && a[p]>a[ls])
{
tar=ls;
}
if((rs)<=n && a[tar]>a[rs])
{
tar=rs;
}
if(tar==p)
return;
swap(a[p],a[tar]);
fix(tar);
}
void make_heap()
{
for(int i=n>>1;i>=1;--i)
{
fix(i);
}
}
void add(int k)
{
a[++n]=k;
int cur=n;
int fa=n>>1;
while(a[fa]>k && fa)
{
swap(a[fa],a[cur]);
cur=fa;
fa=cur>>1;
}
}
void top()
{
printf("%d\n",a[1]);
}
void pop()
{
swap(a[1],a[n]);
--n;
fix(1);
}
int main()
{
// freopen("in.in","r",stdin);
//memset(a,INF,sizeof(a));
m=read();
while(m--)
{
op=read();
switch(op)
{
case 1:add(read());break;
case 2:top();break;
case 3:pop();break;
}
}
// rep(i,1,n)
// cout<<a[i]<<" ";
// cout<<endl;
}j