目錄

簡介

priority_queue 的使用

泛型算法make_heap()、push_heap()、pop_heap()

make_heap()

push_heap()

pop_heap()

---

簡介

priority_queue 是一個擁有權值觀念的 queue，它允許加入新的元素、移除舊的元素、查看 priority_queue 中權值之最的元素等功能。priority_queue 只允許在底端加入元素，并從頂端取出元素，除此之外沒有其它存取元素的途徑。

priority_queue 提供常數時間的最大元素(默認)查找，對數代價的插入與釋放。可為用戶提供的?compare?更改順序，例如，用?std::greater<T>?將導致最小元素作為?top() 出現。用?priority_queue?工作類似管理某些隨機訪問容器中的堆，優勢是不可能突然把堆非法化。

雖然priority_queue 的名字中帶有 queue，但是其底層的邏輯結構是堆。缺省情況下 priority_queue 利用一個大頂堆完成(底層存儲結構是 vector)。堆結構能滿足 priority_queue 所需要的”按照權值高低自動排序”的特性。這里要弄清楚的一點是：priority_queue 底層缺省使用 vector存 儲數據，這是它的存儲結構。而在邏輯上，它將序列視為一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的關系，在當前無序區間中選擇關鍵字最大(或最小)的元素。

關于堆的數據結構，可以看這篇博客：通俗易懂的講解堆排序(含Gif圖)

priority_queue 的所有元素，進出都有一定的規則，只有其頂端的元素，才有機會被外界取用。同時，priority_queue 不提供遍歷功能，也沒有迭代器。由于 priority_queue 完全以底部容器為根據(被歸類為容器適配器)，再加上 heap 處理規則，所以實現非常簡單。STL 源碼很簡短，此處完整列出：

template < class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type> > class priority_queue { public:typedef typename Sequence::value_type value_type;typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference; protected:Sequence c; //底層容器Compare comp; //元素大小比較 public:priority_queue() : c() {}explicit priority_queue(const Compare& x) : c(), comp(x) {}//以下用到的 make_heap(), push_heap(), pop_heap() 都是泛型算法//任意一個構造函數都立刻于底層容器內產生一個 implicit representation heaptemplate <class InputIterator>priority_queue(InputIterator first, InputIterator last, const Compare& x)　: c(first, last), comp(x) { make_heap( c.begin(), c.end(), comp); }template <class InputIterator>priority_queue(InputIterator first, InputIterator last)　: c(first, last){ make_heap( c.begin(), c.end(), comp); }bool empty() const { return c.empty(); }size_type size() const { return c.size(); }const_reference top() const { return c.front(); }void push( const value_type& x ){__STL_TRY{//push_back 是泛型算法，先利用底層容器的 push_back() 將新元素//插入末端，再重排 heap。c.push_back();push_heap( c.begin(), c.end(), comp );}__STL_UNWIND( c.clear() );}void pop(){__STL_TRY{//pop_heap 是泛型算法，從 heap 中取出一個元素，它并不是真正的將//元素彈出，而是重排 heap，然后再以底層容器的 pop_back() 取得被彈出的元素。pop_heap( c.begin(), c.end(), comp );c.pop_back();}__STL_UNWIND( c.clear() );} };

?

?

priority_queue 的使用

?

top?返回到 priority_queue 頂元素的引用

const_reference top()?const;

此元素將在調用?pop()?時被移除。若使用默認比較函數，則返回的元素亦為優先隊列中最大的元素。

?

empty?檢查底層容器是否為空

[[nodiscard]]?bool?empty()?const;

?

size?返回底層容器中的元素數

size_type size()?const;

?

push 添加給定的元素?value?到 priority_queue 中

void?push(?const?value_type&?value?); void?push(?value_type&&?value?);

(1)?等效地調用?c.push_back(value);?std::push_heap(c.begin(), c.end(), comp);

(2)?等效地調用?c.push_back(std::move(value));?std::push_heap(c.begin(), c.end(), comp);

?

pop?從 priority_queue 移除堆頂元素

void?pop();

等效地調用?std::pop_heap(c.begin(), c.end(), comp);?c.pop_back();?。

?

emplace 添加新元素到 priority_queue

template<?class...?Args?> void?emplace(?Args&&...?args?);

原位構造元素，即不進行移動或復制操作。以與提供給函數者準確相同的參數調用元素的構造函數。

?

swap?交換容器適配器與?other?的內容

void?swap(?priority_queue&?other?)?noexcept(/* see below */);

?

代碼:

#include <functional> #include <queue> #include <vector> #include <iostream>template<typename T> void print_queue(T& q) {while(!q.empty()) {std::cout << q.top() << " ";q.pop();}std::cout << '\n'; }int main() {std::priority_queue<int> q;for(int n : {1,8,5,6,3,4,0,9,7,2})q.push(n);print_queue(q);std::priority_queue<int, std::vector<int>, std::greater<int> > q2;for(int n : {1,8,5,6,3,4,0,9,7,2})q2.push(n);print_queue(q2);// 用 lambda 比較元素。auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);for(int n : {1,8,5,6,3,4,0,9,7,2})q3.push(n);print_queue(q3);}輸出： 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 8 9 6 7 4 5 2 3 0 1

?

?

泛型算法 make_heap()、push_heap()、pop_heap()

make_heap()

template<?class?RandomIt?> constexpr?void?make_heap(?RandomIt first, RandomIt last?);template<?class?RandomIt,?class?Compare?> constexpr?void?make_heap(?RandomIt first, RandomIt last, Compare comp?);

make_heap() 在范圍?[first, last)?中構造堆。Compare有兩種參數，一種是greater(生成小頂堆)，一種是less(生成大頂堆)。之后的參數含義相同，不再贅述。

#include <iostream> #include <algorithm> #include <functional> #include <vector>int main() {std::cout << "Max heap:\n";std::vector<int> v { 3, 2, 4, 1, 5, 9 };std::cout << "initially, v: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n';std::make_heap(v.begin(), v.end());std::cout << "after make_heap, v: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n';std::pop_heap(v.begin(), v.end());std::cout << "after pop_heap, v: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n';auto top = v.back();v.pop_back();std::cout << "former top element: " << top << '\n';std::cout << "after removing the former top element, v: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n' << '\n';std::cout << "Min heap:\n";std::vector<int> v1 { 3, 2, 4, 1, 5, 9 };std::cout << "initially, v1: ";for (auto i : v1) std::cout << i << ' ';std::cout << '\n';std::make_heap(v1.begin(), v1.end(), std::greater<>{});std::cout << "after make_heap, v1: ";for (auto i : v1) std::cout << i << ' ';std::cout << '\n';std::pop_heap(v1.begin(), v1.end(), std::greater<>{});std::cout << "after pop_heap, v1: ";for (auto i : v1) std::cout << i << ' ';std::cout << '\n';auto top1 = v1.back();v1.pop_back();std::cout << "former top element: " << top1 << '\n';std::cout << "after removing the former top element, v1: ";for (auto i : v1) std::cout << i << ' ';std::cout << '\n'; }輸出： Max heap: initially, v: 3 2 4 1 5 9 after make_heap, v: 9 5 4 1 2 3 after pop_heap, v: 5 3 4 1 2 9 former top element: 9 after removing the former top element, v: 5 3 4 1 2 Min heap: initially, v1: 3 2 4 1 5 9 after make_heap, v1: 1 2 4 3 5 9 after pop_heap, v1: 2 3 4 9 5 1 former top element: 1 after removing the former top element, v1: 2 3 4 9 5

?

push_heap()

template<?class?RandomIt?> constexpr?void?push_heap(?RandomIt first, RandomIt last?);template<?class?RandomIt,?class?Compare?> constexpr?void?push_heap(?RandomIt first, RandomIt last, Compare comp?);

push_heap() 插入位于位置?last-1?的元素到范圍?[first, last-1)?所定義的堆中。

#include <iostream> #include <algorithm> #include <vector>int main() {std::vector<int> v { 3, 1, 4, 1, 5, 9 };std::make_heap(v.begin(), v.end());std::cout << "v: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n';v.push_back(6);std::cout << "before push_heap: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n';std::push_heap(v.begin(), v.end());std::cout << "after push_heap: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n'; }輸出： v: 9 5 4 1 1 3 before push_heap: 9 5 4 1 1 3 6 after push_heap: 9 5 6 1 1 3 4

?

pop_heap()

template<?class?RandomIt?> constexpr?void?pop_heap(?RandomIt first, RandomIt last?);template<?class?RandomIt,?class?Compare?> constexpr?void?pop_heap(?RandomIt first, RandomIt last, Compare comp?);

pop_heap()交換在位置?first?的值和在位置?last-1?的值，并令子范圍?[first, last-1)?變為堆。

#include <iostream> #include <algorithm> #include <vector>int main() {std::vector<int> v { 3, 1, 4, 1, 5, 9 };std::make_heap(v.begin(), v.end());std::cout << "v: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n';std::pop_heap(v.begin(), v.end()); // 移動最大元素到結尾std::cout << "after pop_heap: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n';int largest = v.back();v.pop_back(); // 實際移出最大元素std::cout << "largest element: " << largest << '\n';std::cout << "heap without largest: ";for (auto i : v) std::cout << i << ' ';std::cout << '\n'; }輸出： v: 9 5 4 1 1 3 after pop_heap: 5 3 4 1 1 9 largest element: 9 heap without largest: 5 3 4 1 1

?

總結

以上是生活随笔為你收集整理的C++ priority_queue 的使用和源码详解的全部內容，希望文章能夠幫你解決所遇到的問題。

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