在 C++ 中,priority_queue
是一個容器適配器,它提供了優先級隊列的數據結構。priority_queue
默認是一個最大堆(max heap),也就是說,隊列頂部的元素總是最大的。如果你想要實現最小堆(min heap),你可以傳遞一個比較函數給 priority_queue
的構造函數。
下面是一個使用 priority_queue
實現優先級排序的例子:
#include <iostream>
#include <queue>
int main() {
// 創建一個最大堆
std::priority_queue<int> pq;
// 向堆中添加元素
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
pq.push(5);
pq.push(9);
pq.push(2);
pq.push(6);
pq.push(5);
pq.push(3);
pq.push(5);
// 輸出堆中的元素
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
return 0;
}
在這個例子中,我們創建了一個 priority_queue<int>
,然后向其中添加了一些整數。由于 priority_queue
是一個最大堆,所以隊列頂部的元素總是最大的。因此,當我們輸出堆中的元素時,它們是按照從大到小的順序排列的。
如果你想要實現最小堆,你可以傳遞一個比較函數給 priority_queue
的構造函數,如下所示:
#include <iostream>
#include <queue>
int main() {
// 創建一個最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
// 向堆中添加元素
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
pq.push(5);
pq.push(9);
pq.push(2);
pq.push(6);
pq.push(5);
pq.push(3);
pq.push(5);
// 輸出堆中的元素
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
return 0;
}
在這個例子中,我們創建了一個 priority_queue<int, std::vector<int>, std::greater<int>>
,其中 std::greater<int>
是一個比較函數,它會導致 priority_queue
成為一個最小堆。因此,當我們輸出堆中的元素時,它們是按照從小到大的順序排列的。