二叉堆

二叉堆是一棵完全二叉树。大根堆:对于每一棵子树,有他的根节点大于所有非根节点。小根堆则相反。请注意二叉堆不等同于二叉搜索树——其中序遍历并不一定有序。下图是一个小根堆:

二叉堆

堆的存在可以让我们快捷地找到他的最值(小根堆:最小值;大根堆:最大值;同时不必局限于数字的大小,而可以拓广到依题目所定的优先级),即为堆顶(根)的值。我们可以对节点进行编号,从而快捷地找到一个节点的左子节点编号为自己的两倍,右子节点(如果有的话)为自己的两倍加一。可见一棵完全二叉树的高度为节点个数 \(n\) 以二为底的对数 \(\log n\)。

堆还支持插入、删除操作。

插入

在上图的堆中再插入一个 \(1\) 应该怎么做?

首先我们应该意识到,这个堆可以用一个一维的数组储存:\(heap\{ 1,3,2,4,7,6,5,8,10,9\}\)。如上面所说,要找到 heap[3]=2 的左儿子 6 只需要 heap[3*2]=heap[6]=6。

我们可以暂且把待插入的 1 放到堆的最后一个元素之后,相当于是 7 的右儿子。发现 7 比 1 要大,不满足小根堆的性质,于是交换 1 和 7。这时又发现 3 比 1 要大,于是交换 1、3。这时发现 1 与 1 相等,不必互换,于是就放好了。

总结一下:

  1. 把待插入的数放到数组 heap 的末尾;
  2. 如果发现比他的父亲小,那么与他的父亲互换;重复这个判断步骤直至满足二叉堆的性质。
const int N=1e6+5;
int Size=0;
int heap[N];
void Add(int x){
	heap[++Size]=x;
	int now=Size,nxt;
	while(now!=1){
		nxt=now>>1;
		if(heap[nxt]>heap[now]) swap(heap[now],heap[nxt]);
		else break;
		now=nxt;
	}
}

删除

二叉堆

在上图删除堆顶的 \(1\) 应该怎么做?

肯定不可以直接把数组的第一个元素删除,因为这样会打乱整个堆。在代码实现中,首先将堆顶的 1 与数组末尾的 7 交换,然后踢掉现在居于数组末尾的 1。把堆顶的 7 进行调整:发现 7 比 1 和 2 都大,应该和谁交换呢?先试试跟 2 交换,发现此时 2 又比 1 大,于是成功地被绕晕了;再试试跟 1 交换,发现至少 [1,2,7] 这一块是满足堆的性质了,感到满意。所以记住了,当根比左右儿子大时,应该跟较小的那个交换。好,交换完了,又发现 7 比 4、3 大,于是交换 7、3。这时已经满足堆的性质了,删除操作执行完毕。

void Pop(){
	swap(heap[1],heap[Size]);
	Size--;
	int now=1,nxt;
	while((now<<1)<=Size){
		nxt=now<<1;
		if(nxt+1<=Size && heap[nxt+1]<heap[nxt]) nxt++;
		if(heap[nxt]<heap[now]) swap(heap[nxt],heap[now]);
		else break;
		now=nxt;
	}
}

取堆顶最值

即 heap[1]。

完整代码

模板在 P3378

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int Size=0;
int heap[N];
void Add(int x){
	heap[++Size]=x;
	int now=Size,nxt;
	while(now!=1){
		nxt=now>>1;
		if(heap[nxt]>heap[now]) swap(heap[now],heap[nxt]);
		else break;
		now=nxt;
	}
}
void Pop(){
	swap(heap[1],heap[Size]);
	Size--;
	int now=1,nxt;
	while((now<<1)<=Size){
		nxt=now<<1;
		if(nxt+1<=Size && heap[nxt+1]<heap[nxt]) nxt++;
		if(heap[nxt]<heap[now]) swap(heap[nxt],heap[now]);
		else break;
		now=nxt;
	}
}
int main()
{
	int n,opt,x;
	cin>>n;
	while(n--){
		cin>>opt;
		if(opt==1) cin>>x,Add(x);
		if(opt==2) cout<<heap[1]<<endl;
		if(opt==3) Pop();
	}
	//堆排序: 
	//while(Size--) cout<<heap[1]<<' ',Pop();
	return 0;
}

练习

题面在 P1081 黑匣子

朴素思路:建一个小根堆,对于每一次询问第 k 小值,首先进行 k-1 次删除操作,然后取堆顶,在把之前删过的元素放回去。这样复杂度太高了!据说只能得到 30pts。

正确思路:

  1. 建一个小根堆和一个大根堆;
  2. 我们可以把当前已有的数列中前 k 小的放入大根堆,那么堆顶显然就是第 k 小;
  3. 所以我们只需要在不断新加元素的过程中,让大根堆中永远是当前的前 k 小就好了;
  4. 循环嵌套,外层枚举 1~n。每次就把 \(a_{u_{i-1}+1}\sim a_{u_i}\) 全部加到小根堆中,然后再去看怎么样让大根堆中全部都是前 i 小,小根堆中全部都是其他;
  5. 我们把小根堆中最小的元素——堆顶放入大根堆,但这时并不一定满足,我们需作一定调整。如果小根堆的堆顶比大根堆的堆顶要小,那么说明小根堆中有比大根堆中要小的数,需要把大根堆的那个数移到小根堆来,小根堆中那个更小的数移到大根堆去。因此不断地交换小根堆堆顶和大根堆堆顶,直至小根堆堆顶大于等于大根堆堆顶;这样最后就可以维护大根堆。
  6. 维护完毕后输出大根堆堆顶,即为第 i 小。
  7. 复杂度:约 \(O(n+m+n\log m)\)。

代码实现:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],u[N],ans[N];
struct smallheap {
	int heap[N],Size;
	void Add(int x){
		heap[++Size]=x;
		int now=Size,nxt;
		while(now!=1){
			nxt=now>>1;
			if(heap[nxt]>heap[now]) swap(heap[nxt],heap[now]);
			else break;
			now=nxt;
		}
	}	
	int Get(){
		int res=heap[1];
		swap(heap[1],heap[Size]);
		Size--;
		int now=1,nxt;
		while((now<<1)<=Size){
			nxt=now<<1;
			if(nxt+1<=Size && heap[nxt+1]<heap[nxt]) nxt++;
			if(heap[nxt]<heap[now]) swap(heap[nxt],heap[now]);
			else break;
			now=nxt;
		}
		return res;
	}
}s;
struct bigheap {
	int heap[N],Size;
	void Add(int x){
		heap[++Size]=x;
		int now=Size,nxt;
		while(now!=1){
			nxt=now>>1;
			if(heap[nxt]<heap[now]) swap(heap[nxt],heap[now]);
			else break;
			now=nxt;
		}
	}	
	int Get(){
		int res=heap[1];
		swap(heap[1],heap[Size]);
		Size--;
		int now=1,nxt;
		while((now<<1)<=Size){
			nxt=now<<1;
			if(nxt+1<=Size && heap[nxt+1]>heap[nxt]) nxt++;
			if(heap[nxt]>heap[now]) swap(heap[nxt],heap[now]);
			else break;
			now=nxt;
		}
		return res;
	}
}t;
int main()
{
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>u[i];
	s.Size=t.Size=0;
	for(int i=1,j=1;i<=n;i++){
		while(j<=u[i]) s.Add(a[j++]);
		t.Add(s.Get());
		int v1,v2;
		while(s.Size && s.heap[1]<t.heap[1]){
			v1=s.Get(),v2=t.Get();
			s.Add(v2),t.Add(v1);
		}
		ans[i]=t.heap[1];
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
	return 0;
}
上一篇:freeRTOS系列教程之【第二章】内存管理


下一篇:最短路径算法