
上QQ阅读APP看本书,新人免费读10天
设备和账号都新为新人
原理2 优先队列详解
普通的队列是一种先进先出的数据结构,从队尾入队,从队头出队。在优先队列中,元素被赋予优先级,优先级高的元素先出队。上节介绍了优先队列的实现原理,在实际的算法实现中,可以直接调用C++中的STL函数priority_queue,在Java中也提供了优先队列接口PriorityQueue。
优先队列priority_queue的成员函数如下。
• empty():若优先队列为空,则返回真。
• pop():出队。
• push():入队。
• top():取堆顶(队头),返回优先队列中优先级最高的元素。
• size():返回优先队列中元素的个数。
优先队列的用法:

其中,第1个参数为数据类型,第2个参数为容器类型,第3个参数为比较函数。后两个参数根据需要也可以省略。

如何控制优先队列的优先级?若不是最大值优先,则可以采用下面4种方法。
(1)使用C++自带的库函数<functional>。首先,在头文件中引用include库函数:

functional提供了以下基于模板的比较函数对象。
• equal_to<Type>:等于。
• not_equal_to<Type>:不等于。
• greater<Type>:大于。
• greater_equal<Type>:大于或等于。
• less<Type>:小于。
• less_equal<Type>:小于或等于。
其次,创建优先队列:

注意:“>>”会被认为错误,它是右移运算符,这里用空格号隔开,表示的含义不同。
(2)自定义优先级①,队列元素为数值型:

创建优先队列:

(3)自定义优先级②,队列元素为结构体类型:

创建优先队列:

(4)自定义优先级③,队列元素为结构体类型:

创建优先队列:
