手写堆

131 阅读2分钟

操作种类

  1. 对给定的数组在O(nlogn)O(nlogn)时间内建堆
  2. 对已有的堆支持插入,删除,查找操作

实现

建堆操作

根据规律,含有n个元素的完全二叉树n2+1n\frac{n}{2}+1\cdots 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