[STL]priority_queue

---

由于merge k sorted lists要用到優(yōu)先隊列，所以參看各種博客。現(xiàn)在總結(jié)一下。

按默認規(guī)定，priority_queue簡單地用<<script type="math/tex" id="MathJax-Element-3"><</script>運算符做元素比較。

根據(jù)這里：

class mycomparison {bool reverse;public:mycomparison(const bool& revparam=false){reverse=revparam;}bool operator() (const int& lhs, const int&rhs) const{if (reverse) return (lhs>rhs);else return (lhs<rhs);} };void testPQ() {int myints[]= {10,60,50,20};priority_queue<int> first;priority_queue<int> second (myints,myints+4);priority_queue<int, std::vector<int>, std::greater<int> >third (myints,myints+4);// using mycomparison:typedef std::priority_queue<int,vector<int>,mycomparison> mypq_type;mypq_type fourth(myints,myints+4); // less-than comparisonmypq_type fifth (myints,myints+4, mycomparison(true)); // greater-than comparison//emptycout << "first: " << endl;while (!first.empty()){cout << first.top() << " ";first.pop();}cout << endl;//default maxHeapcout << "second: " << endl;while (!second.empty()){cout << second.top() << " ";second.pop();}cout << endl;//minHeapcout << "third: " << endl;while (!third.empty()){cout << third.top() << " ";third.pop();}cout << endl;//less than maxHeap-DIYcout << "fourth: " << endl;while (!fourth.empty()){cout << fourth.top() << " ";fourth.pop();}cout << endl;//greater than minHeap-DIYcout << "fifth: " << endl;while (!fifth.empty()){cout << fifth.top() << " ";fifth.pop();}cout << endl; }

程序的輸出結(jié)果：

first為空，second默認為最大堆，third用greater(要include <functional>)變成最小堆，fourth和fifth用的都是自定義的比較函數(shù)，mycomparison是一個類，重載operator()。如果參數(shù)為true，即lhs>rhs，即greater，為最小堆。

對于自定義的類型，也同樣可以插入優(yōu)先隊列。比如現(xiàn)在要把

struct Node {int val;Node* next;Node(int x) : val(x), next(NULL) {} };

根據(jù)val值插入到最小堆（當(dāng)然更準確的描述應(yīng)該是val值越小，越先到達top()）。

有兩種方法：

改變node結(jié)構(gòu)體，重載<<script type="math/tex" id="MathJax-Element-4"><</script>，修改成：

struct Node {int val;Node* next;bool operator < (const Node &x) const {return val > x.val;}Node(int x) : val(x), next(NULL) {} };

測試函數(shù)：

void testPq() {priority_queue<Node, vector<Node>> pq;int a[6] = {5, 6, 8, 10, 230, 0};for (int i = 0; i < 6; i++)pq.push(Node(a[i]));while (!pq.empty()){Node temp = pq.top();pq.pop();cout << temp.val << " ";}cout << endl; }

輸出為：

2. 重新定義一個比較類。

class nodeComparison {//此函數(shù)要加上public。//“>”說明是最小堆。“<”說明是最大堆 public: bool operator() (Node &n1, Node &n2){return n1.val > n2.val;} };

測試函數(shù)同上。初始化priority_queue的時候有一點不同：

priority_queue<Node, vector<Node>, nodeComparison> pq;

如果要push進priority_queue的是Node型指針。則要定義一個比較類了：

class nodeComparison {//此函數(shù)要加上public。//“>”說明是最小堆?！?lt;”說明是最大堆 public: bool operator() (Node* n1, Node* n2){return n1->val > n2->val;} };

綜上，如果是基本內(nèi)置類型，可以用less,greter或者再定義一個比較類，重載operator()。如果是自定義類型，則直接定義一個比較類。The CPP Languages P414,424

參考：
http://www.cnblogs.com/cszlg/archive/2012/07/27/2611607.html

總結(jié)

以上是生活随笔為你收集整理的[STL]priority_queue的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。