priority_queue的用法
priority_queue調用 STL裡面的 make_heap(), pop_heap(), push_heap() 算法實作,也算是堆的另外一種形式。先寫一個用 STL 裡面堆算法實作的與真正的STL裡面的 priority_queue用法相似的priority_queue, 以加深對 priority_queue 的了解
|
STL裡面的 priority_queue 寫法與此相似,隻是增加了模闆及相關的疊代器什麼的。
priority_queue 對于基本類型的使用方法相對簡單。他的模闆聲明帶有三個參數:
priority_queue<Type, Container, Functional>
其中Type 為資料類型, Container 為儲存資料的容器,Functional 為元素比較方式。
Container 必須是用數組實作的容器,比如 vector, deque 但不能用 list.
STL裡面預設用的是 vector. 比較方式預設用 operator< , 是以如果你把後面倆個 參數預設的話,
優先隊列就是大頂堆,隊頭元素最大。
|
如果要用到小頂堆,則一般要把模闆的三個參數都帶進去。
STL裡面定義了一個仿函數 greater<>,對于基本類型可以用這個仿函數聲明小頂堆
|
對于自定義類型,則必須自己重載 operator< 或者自己寫仿函數
|
自定義類型重載 operator< 後,聲明對象時就可以隻帶一個模闆參數。
但此時不能像基本類型這樣聲明
priority_queue<Node, vector<Node>, greater<Node> >;
原因是 greater<Node> 沒有定義,如果想用這種方法定義 則可以按如下方式:
|