欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉堆与优先队列

程序员文章站 2024-02-16 08:39:10
...

概念:

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

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

存储方式:

根据完全二叉树的性质,我们直接按层存储,将二叉堆用一个数组保存。在这种存储方式中,父节点的编号等于子节点的编号除以二,左子节点的编号等于父节点的编号*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)。