原理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）自定义优先级③，队列元素为结构体类型：

创建优先队列：