二叉堆与优先队列

概念：

二叉堆：是一种支持插入、删除、查询最值的数据结构。它其实是一棵满足堆性质的完全二叉树。若树中的任意一个节点的权值都小于等于其父节点的权值，则称该二叉树满足“大根堆性质”（反之则是小根堆）。

优先队列：可以理解为一个大根二叉堆。

存储方式：

根据完全二叉树的性质，我们直接按层存储，将二叉堆用一个数组保存。在这种存储方式中，父节点的编号等于子节点的编号除以二，左子节点的编号等于父节点的编号*2，右子节点的编号等于父节点的编号*2+1。

举个栗子：

a:25 23 10 12 13 7 5 2 3 2 1 2 0 3 5

n:15

如图就是一个满足大根堆性质的二叉堆。

插入、删除元素：

定义：int q[maxn],n;//下面的操作以大根堆为例。

insert(int val):

向二叉堆里插入一个权值为val的新节点。我们可以直接将该点放在堆数组的末位，在通过与父节点交换元素来满足大根堆或小根堆性质。

代码如下：

inline void up(int p) { //向上调整
	while(p>1) { //假设当前节点不是根则继续
		if(q[p]>q[p/2]) { //不满足大根堆性质
			swap(q[p],q[p/2]); //交换
			p/=2; //向上一层
		}
		else break; //满足大根堆性质，直接退出
	}
}

inline void insert(int val) { //插入一个权值为val的节点
	q[++n]=val; //将该节点插入数组末位
	up(n);
}

通过二叉树性质可得，该操作时间复杂度为O(log n)。

extract():

将堆顶从二叉堆中删除。我们可以将堆顶元素与堆尾元素交换，是n--，再向下调整，直至满足大根堆性质或小根堆性质。

代码如下：

inline void down(int p) { //向下调整 
	int son=p*2; //p的左子节点 
	while(son<=n) { //当当前元素位于堆中进行 
		if(son<n && q[son]<q[son+1]) son++; //取左右节点的较大值
		if(q[son]>q[p]) { //不满足大根堆性质 
			swap(q[son],q[p]); //交换
			p=son,son*=2; //向下一层 
		} 
		else break; //以满足大根堆性质则直接退出 
	}
}

inline void extract() {
	q[1]=q[n--]; //将堆首元素与堆尾元素交换
	down(1); 
}

通过二叉树性质可得，该操作时间复杂度为O(log n)。

remove(p)：

将a[p]从堆中删除。将a[p]与堆尾元素交换，并把n--。此时需要把数组既向上调整，再向下调整。

代码如下：

inline void remove(int p) {
	q[p]=q[n--]; //将q[p]与堆尾元素交换，并把n-- 
	up(p),down(p); //这下知道为什么要把insert和extract分两个函数写了吧 
}

该操作时间复杂度为前两个操作的时间复杂度之和。

get_top:

返回二叉堆堆顶权值，即a[1]。

inline int get_top() {
    return q[1]; //返回最大值
}

该操作时间复杂度为O(1)。

STL：

C++STL中priority_queue，即优先队列，就已经实现了一个大根堆，支持insert，extract和get_top操作，不支持remove，具体如下：

头文件及定义：

#include<queue>

priority_queue<int> q;//定义一个叫q的二叉堆

插入一个叫val的元素：

q.push(val);

该操作时间复杂度同insert，为O(log n)。

删除堆顶元素：

q.pop();

该操作时间复杂度同extract，为O(log n)。

是x等于堆顶元素：

int x=q.top();

该操作时间复杂度同get_top，为O(1)。