通过c++STL的堆来维护一个堆,实现大堆序,并输出其中最大的数字,和插入,删除修改了一个其中数字后输出最大数字
时间: 2024-09-24 16:29:38 浏览: 28
在C++中,可以使用标准模板库(STL)中的`priority_queue`来创建一个大顶堆(也称为最小堆),这种数据结构的特点是最顶部元素总是具有最小值。如果你想维护并获取最大值,你需要使用`greater<>`模板来指定降序排列。以下是基本步骤:
首先,需要包含必要的头文件:
```cpp
#include <iostream>
#include <queue>
using namespace std;
```
然后定义一个`max_heap`类,用于存储和操作大堆:
```cpp
class MaxHeap {
private:
priority_queue<int, vector<int>, greater<int>> heap;
public:
// 插入元素
void insert(int value) {
heap.push(value);
}
// 获取最大值
int getMax() const {
return heap.top();
}
// 删除最大值
void removeMax() {
if (!heap.empty()) {
heap.pop();
}
}
// 修改最大值
void updateMax(int new_value) {
if (!heap.empty()) {
heap.top() = new_value;
} else {
insert(new_value); // 如果堆为空,则直接插入
}
}
};
```
现在你可以创建一个`MaxHeap`实例,并进行操作:
```cpp
int main() {
MaxHeap h;
// 插入元素示例
h.insert(5);
h.insert(3);
h.insert(7);
// 输出最大值
cout << "Current max: " << h.getMax() << endl; // 输出:7
// 删除最大值并更新
h.removeMax();
h.updateMax(10);
// 再次输出最大值
cout << "After removing and updating: " << h.getMax() << endl;
return 0;
}
```
运行上述程序,你会看到每次修改后的最大值。
阅读全文