数据结构-堆详解

堆

图片：

二叉堆的父节点为这个子树的最值。

如何维护它。
我们发现它是一棵二叉树，那就自然满足若父节点为 $x$ 则左儿子节点为 $x\times 2$ 右儿子为 $x\times 2+1$ 这是显然的，但如果写成指针或结构体就太麻烦了，所以考虑用数组来维护它。

用一个数组 $T$ 来存储这颗二叉树，根节点为 $T_1$ 根据二叉树的性质对于每个子节点 $x$ 则有：

1. 若 $x>1$ 则fa[x]=i/2;
2. 若 $2\times x>n$ 则 $x$ 没有儿子，如果 $2\times x+1>n$ 则 $x$ 没有右儿子。
3. 如果节点 $x$ 有孩子，则 $x$ 的左儿子为 $x\times 2$ 右儿子为 $x\times 2+1$

复杂度分析：

这样做由于二叉树只有 ${\log }_{2}n$ 层，自然单次复杂度为 $O({\log }_{2}n)$可以解决 $n\le 10^6$ 及以下的问题。

那么该如何让这个二叉树平衡？通常使用上浮法与下沉法。
例子：
假设你已经有一个堆了，就是上面那个

这个时候你如果想要给它加入一个节点怎么办，比如说0？

先插到堆底（严格意义上来说其实0是在5的左儿子的，图没画好放不下去，不过也不影响）

然后你会发现它比它的父亲小啊，那怎么办？不符合小根堆的性质了啊，那就交换一下他们的位置

交换之后还是发现不符合小根堆的性质，那么再换

还是不行，再换

好了，这下就符合小根堆的性质了。

事实上堆的插入就是把新的元素放到堆底，然后检查它是否符合堆的性质，如果符合就丢在那里了，如果不符合，那就和它的父亲交换一下，一直交换交换交换，直到符合堆的性质，那么就插入完成了。
删除同理这里不在复述了。

代码：

插入：

void push(int x){
	h[++len] =x;
	int i=len;
	while(i>1 && h[i]<h[len/2]){
		swap(h[i],h[i/2]);
		i/=2;
	}
}
1
2
3
4
5
6
7
8

删除：

void pop(){
	h[1] = h[len--];
	int i=1;
	while((i<<1)<=len){
		int son=(i<<1);
		if(son<len&&h[son+1]<h[son]){
			son++;
		}
		if(h[son]<h[i]){
			swap(h[son],h[i]);
			i=son;
		}
		else break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

STL堆：

算法竞赛中虽然STL没有手写快但是否好像实用代码：

定义一个大根堆即堆内为递减的序列

priority_queue<int> Q;

小根堆：

priority_queue<int,vector<int>,greater<int>> Q2;

使用：

插入一个数：

void insert(int x){
	q.push(x);
}
1
2
3

删除堆头：

void erase(){
	q.pop();
}
1
2
3

访问堆头

int front(){
	return q.top();
}
1
2
3

建议使用STL的堆