C++中的priority_queue
是一個容器適配器,它提供了常數時間查找最大元素(在std::greater
比較器下為最小元素)的能力,并且可以在對數時間內插入和刪除元素
push()
方法將元素添加到priority_queue
中。這將根據比較函數將新元素放置在正確的位置。示例代碼:
#include<iostream>
#include<queue>
int main() {
std::priority_queue<int> pq;
// 插入元素到 priority_queue
pq.push(5);
pq.push(8);
pq.push(3);
pq.push(1);
// priority_queue 中的元素:1, 3, 5, 8
return 0;
}
pop()
方法從priority_queue
中刪除最大(或最小)元素。注意,pop()
只會刪除堆頂元素,而不是指定元素。如果要刪除指定元素,請使用std::make_heap
、std::push_heap
和std::pop_heap
等算法重新實現一個自定義的堆容器。示例代碼:
#include<iostream>
#include<queue>
int main() {
std::priority_queue<int> pq;
pq.push(5);
pq.push(8);
pq.push(3);
pq.push(1);
// priority_queue 中的元素:1, 3, 5, 8
// 刪除堆頂元素(最小值)
pq.pop();
// priority_queue 中的元素:3, 5, 8
return 0;
}
請注意,上述示例中的priority_queue
默認為最大堆。如果需要最小堆,請在聲明priority_queue
時傳遞std::greater<int>
作為模板參數,如下所示:
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;