优先队列

优先队列,第1张

我们知道普通队列的特点是先进先出,但是优先队列的特点则遵守以下两条规则:

- 最大优先队列:无论入队的顺序,当前最大的元素先出列。

- 最小优先队列:无论入队的顺序,当前最小的元素先出列。

说明:在学习优先队列前必须先理解 二叉堆

这时候就是 二叉堆 发挥作用的时候了。我们知道二叉堆有以下特性:

- 最大堆:堆顶是整个数组中最大的元素,且任何父节点的值都大于其子节点

- 最小堆:堆顶是整个数组中最小的元素,且任何父节点的值都小于其子节点

对于优先队列,介绍以下几种 *** 作:

入队 *** 作;

出队 *** 作;

说明:以最小优先队列为例

1.入队 *** 作

优先队列本质上就是用二叉堆来实现的,每次插入一个数据都是插入到数据数组的最后一个位置,然后再做上浮 *** 作,如果插入的数是数组中最大数,自然会上浮到堆顶。如“图1 入队 *** 作”所示:

2.出队 *** 作

出队 *** 作就是返回堆顶最小堆的数据之后用数组最后的数插入到堆顶,之后再做下沉 *** 作。如“图2 出队 *** 作”所示:

因为二叉堆上浮和下沉的时间复杂度都为log2(n),所以入队和出队的时间复杂度也是log2(n)。

优先队列是基于二叉堆实现的,优先指的是按某种优先级优先出列而不是先入先出。 *** 作系统的阻塞机制正是有优先队列实现。

priority_queue又称为优先队列,其底层是用 堆 来进行实现的。在优先队列中,队首元素一定是当前队列中优先级最高的那一个。

当然,可以在任何时候往优先队列里面加入(push)元素,而优先队列底层的数据结构堆(heap)会随时调整结构,使得 每次的队首元素都是优先级最大的。

定义:priority_queue<typename>name

和队列不一样的是,优先队列没有front()和back()函数,而 只能通过top()函数来访问队首元素。

(1)push()

(2)top(): 可以获得队首元素(即堆顶元素)

(3)pop(): 队首元素(即堆顶元素)出队

(4)empty():和queue一样

(5)size():

priority_queue优先级的设置:

下面介绍基本数据类型和结构体类型的优先级设置方法

①基本数据类型的优先级设置

priority_queue<int, vector<int>, less<int>>q        //less<int>表示数字大的优先级越大,而greater<int>表示数字小的优先级越大

priority_queue<int , vector<int >, greater<int>>q   //vector<int>是用来承载底层数据结构堆(heap)的容器

②结构体的优先级设置

完整示例:

此处小于号的重载于排序函数sort中的cmp函数有些类似。事实上,两者的作用确实是类似的, 只不过效果看上去似乎是“相反”的。 在排序中,如果是“return f1.price >f2.price”,那么则是按价格从高到低排序,但是在优先队列中却是把价格低的放到队首。原因在于,优先队列本身默认的规则就是优先级高的放在队首,因此把小于号重载为大于号的功能时只是把这个规则反向了一下。如果读者无法理解,那么不妨记住, 优先队列的这个函数与sort中的cmp函数的效果是相反的。

有没有办法跟sort中的cmp函数那样写在结构体外面呢?

自然是有办法的,只需把friend去掉,把小于号改成一对小括号,再把重载的函数写在结构体外面,同时将其用struct包装起来。


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/bake/11889007.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-19
下一篇 2023-05-19

发表评论

登录后才能评论

评论列表(0条)

保存