c++ 优先队列定义小根堆
时间: 2023-11-03 10:53:54 浏览: 57
在C中,优先队列默认以vector为底层容器,并采用heap处理规则来形成大根堆。如果我们需要定义小根堆,则需要使用STL自带的小根堆,即将vector改为greater<int>,作为比较函数对象的类型。下面是一个示例代码:
```cpp
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int, vector<int>, greater<int>> q;
q.push(3);
q.push(5);
q.push(1);
while (!q.empty()) {
cout << q.top() << endl;
q.pop();
}
return 0;
}
```
运行上述代码,输出结果为1 3 5,符合小根堆的特点。
相关问题
c++优先队列定义小根堆
在C++中,可以使用`std::priority_queue`定义一个小根堆。小根堆和大根堆的主要区别在于比较函数的设置。默认情况下,`std::priority_queue<int>`会构建一个大根堆,其中元素从大到小排序。要定义一个小根堆,可以使用`std::priority_queue<int, std::vector<int>, std::greater<int>>`。这里的`std::greater<int>`是一个函数对象,用于比较元素的顺序。所以完整的定义一个小根堆的代码如下:
```cpp
#include <iostream>
#include <queue>
using namespace std;
void small_heap() {
int source_data = {3, 5, 8, 1, 10, 2, 9, 15, 13, 16};
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
for (auto n : source_data) {
q.push(n);
}
while (!q.empty()) {
cout << q.top() << endl;
q.pop();
}
}
```
在这个例子中,我们使用`std::priority_queue<int, std::vector<int>, std::greater<int>>`定义了一个小根堆`q`。然后将数据逐个插入堆中,并按升序从小到大弹出元素。最终输出的结果是一个从小到大排序的队列。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
c++ 优先队列 小根堆
在C++中,优先队列默认是大根堆,也就是说,队列中的元素按照从大到小的顺序排列。如果想要使用小根堆,需要在定义优先队列时指定底层容器类型为vector,比较函数为greater。下面是一个小根堆的例子:
```
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int, vector<int>, greater<int>> q;
q.push(3);
q.push(5);
q.push(1);
while(!q.empty()) {
cout << q.top() << endl;
q.pop();
}
return 0;
}
```
在这个例子中,我们使用了STL自带的小根堆,因此需要将vector改为greater<int>。其中,vector<int>是指底层容器的类型,而greater<int>是指比较函数对象的类型。
另外,如果想要使用自定义类型的小根堆,需要在定义结构体时重载小于号运算符,如下所示:
```
struct cs {
int x;
bool operator < (const cs &rhs) const {
return x > rhs.x;
}
} a;
priority_queue<cs> Q;
```
这样就可以使用自定义类型的小根堆了。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)