本文參考的源碼版本：gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)。

priority_queue 本質是容器適配器，它對內部容器的元素有自己的管理方式，而 priority_queue 實際維護的是一個二叉堆。STL中 priority_queue 的操作是基于完全二叉樹，使用隨機訪問迭代器訪問元素，二叉堆在創建時按照層序遍歷的順序將數據放入容器中，因此創建 priority_queue 時使用的容器需要具有隨機訪問的特性。

priority_queue 是一個類模板，有三個模板參數，第一個數據的類型，第二個是容器的類型，默認為 vector ，第三個是用于比較操作的函數對象，默認是 less ，即小于比較。

template<typename _Tp, typename _Sequence = vector<_Tp>,typename _Compare = less<typename _Sequence::value_type> >class priority_queue {};

完全二叉樹

如果對滿二叉樹的結點進行編號, 約定編號從根結點起, 自上而下, 自左而右。則深度為 k 的, 有 n 個結點的二叉樹, 當且僅當其每一個結點都與深度為 k 的滿二叉樹中編號從 1 至 n 的結點一一對應時, 稱之為完全二叉樹，換言之如果只刪除了滿二叉樹最底層最右邊的連續若干結點形成的樹稱為完全二叉樹。滿二叉樹是完全二叉樹的特列。完全二叉樹具有以下特性：

• 具有 n 個節點的完全二叉樹的深度為:

$$k=[lo{g}_{2}n{]}_{floor}+1$$

• 第 $i$ 個結點的編號范圍為: $1\le i\le n$ ;
• 如果 $i=1$，$i$ 為根結點，無雙親；如果 $i>1$ ，結點$i$ 的雙親結點為：

$$[i/2{]}_{floor}$$

• 如果$2i<=n$ ，結點i的左孩子為結點 $2i$；否則無左孩子

• 如果 $2i+1<=n$，結點i的右孩子為結點 $2i+1$，否則無右孩子

• 結點 $i$ 所在的層次為:

  $$k_i=[lo{g}_{2}i{]}_{floor}+1$$

• 如果 $i>1$, $i$ 為奇數時，結點 $i$ 為右子結點； $i$ 為偶數時，結點 $i$ 為左子結點

STL的 priority_queue 在實現的時候保證了堆頂的元素始終位于容器的第一個位置，相當于二叉堆的完全二叉樹的位置是從 0 開始計數，與完全二叉樹的計數有細微差別。

堆有序化( reheapifying ) 中的上浮和下沉

當在二叉堆的最后一個位置插入新的元素時，新加入的元素可能會破壞堆的有序性，此時需要對新加結點與其父結點進行比較，如果大于父結點的值，那么就需要交換新加結點和父結點，如此重復比較，直到不再比父結點大時終止。這個過程就是堆有序化過程中的上浮操作。

當在移除二叉堆的堆頂元素時，被移除的元素破壞了堆的有序性，此時需要對堆頂的兩個子結點中選擇較大的值作為新的堆頂，而被選擇的子結點則不能再作為子結點，則需繼續比較其兩個子結點，如此重復比較，直到到達堆底，或者兩個子結點的值都比根結點小。這個過程就是堆有序化過程中的下沉操作。

#include <vector> #include <random> #include <chrono>using namespace std;class PriorityQueue { public:void Push(int value) {v_.emplace_back(value);push_hole(v_.size() - 1,value);}void Pop() {int back = v_.back();int size = v_.size();int hole = 0;int right_child = 2 * (hole + 1); // 計算右孩子結點的位置while (right_child < size) {// 左孩子小于右孩子if (v_[right_child - 1] < v_[right_child]) {v_[hole] = v_[right_child];hole = right_child;} else { // 左孩子大于等于右孩子v_[hole] = v_[right_child - 1];hole = right_child - 1;}right_child = 2 * (hole + 1);}push_hole(hole, back);v_.pop_back(); // 最后才從容器中刪除元素}int Top() const {return v_[0];};;int Empty() const {return v_.empty();}friend ostream &operator<<(ostream &os, const PriorityQueue &rhs) {for (const auto &v: rhs.v_) {os << v << " ";}os << endl;return os;}private:void push_hole(int hole, int value) {int parent = (hole - 1) / 2; // 根據完全二叉樹的特性計算父結點的位置// 父結點比新加的值小，交換父結點和新加入的值while (parent >= 0 && v_[parent] < value) {swap(v_[parent], v_[hole]);hole = parent;parent = (hole - 1) / 2;}v_[hole] = value;}private:vector<int> v_; };int main() {PriorityQueue pq;default_random_engine e(chrono::system_clock::now().time_since_epoch().count());uniform_int_distribution<int> d(1,1000);for (int i = 0; i < 100; i++) {pq.Push(d(e));} // vector<int> v{11,10,3,20,15,15,1,17,9,2,0, // 12,25,11,12,30,0,0,0,60,15, // 22,63,77,60,1,1,2,6,7,4,2,8}; // for (int val : v) { // pq.Push(val); // }cout << "Container: " << pq;cout << "Top: ";while (!pq.Empty()) {int top = pq.Top();pq.Pop();cout << top << " ";}return 0; }

priority_queue 的 push 操作

priority_queue 的 push 操作本質上就是二叉堆有序化的上浮，在真正的 push 前會先在容器的最后一個位置挖一個洞，以作為后續重排容器元素的中轉位置。push 操作步驟如下：

先將要添加的數據添加到容器最后一個位置，相當于挖個洞；

然后對容器進行重排操作，重排操作的過程大致如下：

• 初始時，洞的位置就是容器最后一個位置；
• 如果容器本身是空的，那么在洞的位置添加新的元素后，該元素就堆頂的元素；
• 如果容器本身不是空的，那么就通過洞的位置找到其父結點的位置，然后使用父結點的值與新加入的值進行比較，如果父結點的元素值小于新加入的值，那么就將父結點的值移到挖的洞中，這樣中間位置就形成了一個洞，此時更新洞的位置。然后重復操作，直至洞的位置不再更新。

將新加入的值添加到洞中，完成一次 push 操作。

示例：

下面是 push 重排的關鍵源碼部分，第一個參數是容器的首元素迭代器，第二個參數是洞的初始位置，第三個參數是堆頂，即容器第一個位置，第四個參數是新添加的值，第五個參數是用于進行比較操作的函數對象。從源碼能夠看出，在比較操作的是時候，父結點作為了運算符的左側運算對象，父結點比新加的結點小才會進行相應的操作，也就不難理解為什么 less 比較操作維護的卻是大堆頂。

template<typename _RandomAccessIterator,typename _Distance, typename _Tp,typename _Compare> void __push_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __topIndex,_Tp __value,_Compare& __comp) {_Distance __parent = (__holeIndex - 1) / 2; // 計算父結點索引// 比較父結點和要push的值大小關系while (__holeIndex > __topIndex && __comp(__first + __parent, __value)) {*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));__holeIndex = __parent;__parent = (__holeIndex - 1) / 2;}// 將要push的值添加到洞里面*(__first + __holeIndex) = _GLIBCXX_MOVE(__value);}

priority_queue 的 pop 操作

priority_queue 的 push 操作本質上就是二叉堆有序化的下沉，pop 操作步驟如下：

首先記錄容器最后一個位置的元素值；

將堆頂的元素移動到容器最后一個位置上，這樣堆頂的位置就相當于形成了一個洞；

然后調整堆，調整堆的過程大致如下：

• 首先根據堆頂找到其右孩子結點，然后比較右孩子結點和左孩子結點的值，將兩者中較大的值放置到堆頂;
• 被移走的數值則形成了一個洞，因此需要繼續向下比較，直到最后不再更新洞的位置

將之前記錄的最后一個位置的元素值 push 到最后一個孔的位置；

最后從容器中移除最后一個位置的元素。

示例：

下面是 pop 調整堆的關鍵源碼部分，第一個參數是容器的首元素迭代器，第二個參數是洞的初始位置，第三個參數是容器中除去要移除的元素后剩余的個數，第四個參數記錄的pop前容器最后一個位置的元素，第五個參數是用于進行比較操作的函數對象。

template<typename _RandomAccessIterator, typename _Distance,typename _Tp, typename _Compare> void __adjust_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __len,_Tp __value,_Compare __comp) {const _Distance __topIndex = __holeIndex;_Distance __secondChild = __holeIndex;while (__secondChild < (__len - 1) / 2){// 計算某個父結點的右孩子結點索引__secondChild = 2 * (__secondChild + 1);// 比較左右兩個孩子結點的大小，若左孩子結點大則更新索引if (__comp(__first + __secondChild,__first + (__secondChild - 1)))__secondChild--;*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));__holeIndex = __secondChild;}// 剩余元素個數為偶數，說明完全二叉樹的最后一個位置不是右孩子結點，就只能是左孩子結點// 而如果此時的洞是最后一個位置的父結點，那么就只能將左孩子結點的值移動到父結點處。if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2){__secondChild = 2 * (__secondChild + 1);*(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first+ (__secondChild - 1)));__holeIndex = __secondChild - 1;}__decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp)))__cmp(_GLIBCXX_MOVE(__comp));// 將之前記錄的容器最后一個位置的值填入洞中std::__push_heap(__first, __holeIndex, __topIndex,_GLIBCXX_MOVE(__value), __cmp); }

原文地址

總結

以上是生活随笔為你收集整理的C++ STL实现的优先队列( priority_queue )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。