STL priority_queue底層實現（深度剖析）

priority_queue 優先順序佇列之所以總能保證優先順序最高的元素位於隊頭，最重要的原因是其底層採用堆資料結構儲存結構。

有讀者可能會問，priority_queue 底層不是採用 vector 或 deque 容器儲存資料嗎，這裡又說使用堆結構儲存資料，它們之間不衝突嗎？顯然，它們之間是不衝突的。

首先，vector 和 deque 是用來儲存元素的容器，而堆是一種資料結構，其本身無法儲存資料，只能依附於某個儲存媒介，輔助其組織資料儲存的先後次序。其次，priority_queue 底層採用 vector 或者 deque 作為基礎容器，這毋庸置疑。但由於 vector 或 deque 容器並沒有提供實現 priority_queue 容器介面卡 “First in,Largest out” 特性的功能，因此 STL 選擇使用堆來重新組織 vector 或 deque 容器中儲存的資料，從而實現該特性。

注意，雖然不使用堆結構，通過編寫演算法調整 vector 或者 deque 容器中儲存元素的次序，也能使其具備 “First in,Largest out” 的特性，但執行效率通常沒有使用堆結構高。

那麼，堆到底是什麼，它又是怎樣組織資料的呢？

priority_queue底層的堆儲存結構

以下內容要求讀者對資料結構中的樹儲存結構有一定的了解，如果沒有，請先閱讀《樹儲存結構》一章。

簡單的理解堆，它在是完全二元樹的基礎上，要求樹中所有的父節點和子節點之間，都要滿足既定的排序規則：

• 如果排序規則為從大到小排序，則表示堆的完全二元樹中，每個父節點的值都要不小於子節點的值，這種堆通常稱為大頂堆；
• 如果排序規則為從小到大排序，則表示堆的完全二元樹中，每個父節點的值都要不大於子節點的值，這種堆通常稱為小頂堆；

圖 1 展示了一個由 {10,20,15,30,40,25,35,50,45} 這些元素構成的大頂堆和小頂堆。其中經大頂堆組織後的資料先後次序變為 {50,45,40,20,25,35,30,10,15}，而經小頂堆組織後的資料次序為{10,20,15,25,50,30,40,35,45}。

---