STL容器之优先队列

STL容器之优先队列

优先级队列,以前刷题的时候用的比较熟,现在竟然我只能记得它的关键字是priority_queue(太伤了)。在一些定义了权重的地方这个数据结构是很有用的。

先回顾队列的定义:队列(queue)维护了一组对象,进入队列的对象被放置在尾部,下一个被取出的元素则取自队列的首部。priority_queue特别之处在于,允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部,而是放在比它优先级低的元素前面。标准库默认使用<操作符来确定对象之间的优先级关系,所以如果要使用自定义对象,需要重载 < 操作符。

优先队列有两种,一种是最大优先队列;一种是最小优先队列;每次取自队列的第一个元素分别是优先级最大和优先级最小的元素。

1) 优先队列的定义

包含头文件:”queue.h”, “functional.h”

可以使用具有默认优先级的已有数据结构;也可以再定义优先队列的时候传入自定义的优先级比较对象;或者使用自定义对象(数据结构),但是必须重载好< 操作符。 

2) 优先队列的常用操作

优先级队列支持的操作

q.empty()         如果队列为空,则返回true,否则返回false

q.size()            返回队列中元素的个数

q.pop()             删除队首元素,但不返回其值

q.top()             返回具有最高优先级的元素值,但不删除该元素

q.push(item)     在基于优先级的适当位置插入新元素

其中q.top()为查找操作,在最小优先队列中搜索优先权最小的元素,在最大优先队列中搜索优先权最大的元素。q.pop()为删除该元素。优先队列插入和删除元素的复杂度都是O(lgn),所以很快

另外,在优先队列中,元素可以具有相同的优先权。

下面这个C例子,包含了几乎所有常见的优先队列用法。 

复制代码

复制代码

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz