原理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）自定義優先級③，隊列元素為結構體類型：

創建優先隊列：