C++中实现大根堆常用priority_queue或手动数组实现。优先队列默认为最大堆，使用简单；手动实现通过shiftUp和shiftDown维护堆性质，灵活性高；还可使用make_heap等算法操作容器。
在C++中实现大根堆（最大堆）有多种方式，最常用的是利用标准库中的 priority_queue，也可以手动使用数组和算法实现一个堆结构。下面分别介绍这两种方法。
1. 使用 priority_queue 实现大根堆
C++ STL 中的 priority_queue 默认就是一个大根堆，可以直接使用。
头文件：#include 默认情况下，priority_queue 是基于 vector 的最大堆
示例代码：
#include #include using namespace std;int main() {priority_queue maxHeap;
maxHeap.push(10);maxHeap.push(30);maxHeap.push(20);maxHeap.push(5);while (!maxHeap.empty()) { cout << maxHeap.top() << " "; // 输出：30 20 10 5 maxHeap.pop();}return 0;
}
立即学习“C++免费学习笔记（深入）”；
这个方法简单高效，适用于大多数场景。
2. 手动实现大根堆（基于数组）
如果需要更灵活的控制，比如支持修改元素或实现索引堆，可以手动实现一个大根堆。基本思想是使用数组模拟完全二叉树，并维护堆性质：每个节点的值不小于其子节点的值。
核心操作：
向上调整（shiftUp）：插入元素后，从下往上调整以恢复堆性质向下调整（shiftDown）：删除堆顶后，从上往下调整插入（push）：添加到末尾并 shiftUp弹出（pop）：用最后一个元素替换堆顶，然后 shiftDown
手动实现代码示例：
#include #include using namespace std;class MaxHeap {private:vector heap;
void shiftUp(int index) { while (index > 0) { int parent = (index - 1) / 2; if (heap[index] <= heap[parent]) break; swap(heap[index], heap[parent]); index = parent; }}void shiftDown(int index) { int n = heap.size(); while (index * 2 + 1 < n) { int child = index * 2 + 1; if (child + 1 heap[child]) child++; if (heap[index] >= heap[child]) break; swap(heap[index], heap[child]); index = child; }}
public:void push(int val) {heap.push_back(val);shiftUp(heap.size() - 1);}
void pop() { if (heap.empty()) return; heap[0] = heap.back(); heap.pop_back(); if (!heap.empty()) shiftDown(0);}int top() { if (heap.empty()) throw runtime_error("堆为空"); return heap[0];}bool empty() { return heap.empty();}int size() { return heap.size();}
};
// 使用示例int main() {MaxHeap maxHeap;maxHeap.push(10);maxHeap.push(30);maxHeap.push(20);maxHeap.push(5);
while (!maxHeap.empty()) { cout << maxHeap.top() << " "; // 输出：30 20 10 5 maxHeap.pop();}return 0;
}
立即学习“C++免费学习笔记（深入）”；
3. 使用 make_heap 等算法函数
C++ 还提供了 gorithm> 中的堆操作函数：
make_heap：将一个区间构造成堆push_heap：将新元素加入堆pop_heap：将堆顶移到末尾
示例：
#include #include #include using namespace std;int main() {vector v = {10, 30, 20, 5};make_heap(v.begin(), v.end()); // 构建大根堆
cout << "堆顶: " << v.front() << endl;v.push_back(40);push_heap(v.begin(), v.end());cout << "新堆顶: " << v.front() << endl;pop_heap(v.begin(), v.end());v.pop_back();return 0;
}
立即学习“C++免费学习笔记（深入）”；
基本上就这些。日常开发推荐用 priority_queue，简洁安全；学习或特殊需求可手动实现。理解堆的调整逻辑对算法题很有帮助。
以上就是c++++中如何实现大根堆_c++大根堆实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1477162.html
微信扫一扫 
支付宝扫一扫 
