c++优先队列大根堆创建
时间: 2024-04-24 08:19:28 浏览: 29
C++中的优先队列是一种特殊的数据构,它可以按照元素的优先级进行排序和访问。在C++中,优先队列通常使用大堆来实现。
要创建一个大根堆的优先队列,可以使用C++标准库中的`priority_queue`类模板。`priority_queue`默认使用`less`函数对象来进行元素的比较,即将较大的元素放在队列的前面。
下面是创建大根堆优先队列的示例代码:
```cpp
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> pq; // 创建一个大根堆优先队列
// 向优先队列中插入元素
pq.push(5);
pq.push(2);
pq.push(10);
pq.push(3);
// 访问优先队列中的元素
while (!pq.empty()) {
std::cout << pq.top() << " "; // 输出队列中最大的元素
pq.pop(); // 弹出队列中最大的元素
}
return 0;
}
```
输出结果为:10 5 3 2,说明优先队列按照降序排列元素。
相关问题
c++优先队列大根堆
C++中的优先队列默认是大根堆,因此可以直接使用priority_queue类来创建大根堆。以下是一个简单的示例代码:
```cpp
#include <queue>
using namespace std;
int main(){
priority_queue<int> pq;
pq.push(5);
pq.push(2);
pq.push(7);
while(!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
```
输出结果为:7 5 2,符合大根堆的特点。
如果要使用自定义类型来创建大根堆,可以重载该类型的“<”运算符。以下是一个示例代码:
```cpp
#include <queue>
using namespace std;
struct Node{
int val;
bool operator<(const Node& b) const{
return val < b.val; // 大根堆,val较大的节点排在前面
}
};
int main(){
priority_queue<Node> pq;
pq.push({5});
pq.push({2});
pq.push({7});
while(!pq.empty()){
cout << pq.top().val << " ";
pq.pop();
}
return 0;
}
```
输出结果为:7 5 2,同样符合大根堆的特点。
c++优先队列大根堆代码模板
// 定义一个大根堆类
class MaxHeap {
private:
vector<int> heap; // 使用 vector 存储堆
int size; // 堆的大小
// 工具函数 —— 交换堆中的两个元素
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 工具函数 —— 堆化某一个节点
void heapify(int index) {
int largest = index; // 先将当前节点标记为最大值
int left = index * 2 + 1; // 左孩子节点的索引
int right = index * 2 + 2; // 右孩子节点的索引
// 比较当前节点、左孩子节点和右孩子节点中的最大值
if (left < size && heap[left] > heap[largest]) {
largest = left;
}
if (right < size && heap[right] > heap[largest]) {
largest = right;
}
// 如果当前节点的值不是最大值,则将当前节点和最大值节点交换,并递归地对最大值节点进行堆化
if (largest != index) {
swap(heap[index], heap[largest]);
heapify(largest);
}
}
public:
// 构造函数 —— 建立一个空堆
MaxHeap() {
size = 0;
}
// 获取堆中元素的数量
int getSize() {
return size;
}
// 判断堆是否为空
bool isEmpty() {
return size == 0;
}
// 在堆末尾添加一个元素,并将其上移对其进行调整
void add(int element) {
heap.push_back(element);
size++;
int index = size - 1;
int parent = (index - 1) / 2;
while (index > 0 && heap[index] > heap[parent]) {
swap(heap[index], heap[parent]);
index = parent;
parent = (index - 1) / 2;
}
}
// 获取堆顶元素
int peek() {
if (size == 0) {
throw "Heap is empty.";
}
return heap[0];
}
// 删除堆顶元素,并将堆末尾的元素放到堆顶,然后将其下沉进行调整
int remove() {
if (size == 0) {
throw "Heap is empty.";
}
int root = heap[0];
heap[0] = heap[size - 1];
size--;
heap.pop_back();
heapify(0);
return root;
}
};
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.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)