C++中实现小根堆常用STL的priority_queue，通过greater或自定义比较器实现，默认为大根堆。示例：priority_queue minHeap; 支持基本类型与结构体，后者需重载operator>或定义仿函数。竞赛中可手写数组版堆，用vector模拟完全二叉树，实现上浮插入与下沉删除。日常推荐STL方式，简洁高效；特殊需求再考虑手动实现。
在C++中实现小根堆，最常用的方式是利用标准模板库（STL）中的 priority_queue，并结合自定义比较方式。默认情况下，priority_queue 实现的是大根堆，但通过调整比较器可以轻松转换为小根堆。
使用 priority_queue 实现小根堆
要让 priority_queue 变成小根堆，只需传入 greater 作为第三个模板参数。
包含头文件：#include 和 #include 声明格式：priority_queue, greater> minHeap;
示例代码：
#include #include #include #includeusing namespace std;
立即学习“C++免费学习笔记（深入）”；
int main() {priority_queue<int, vector, greater> minHeap;
minHeap.push(10);minHeap.push(5);minHeap.push(15);while (!minHeap.empty()) { cout << minHeap.top() << " "; minHeap.pop();}// 输出：5 10 15return 0;
}
自定义结构体的小根堆
如果需要对结构体或类类型建小根堆，可以通过重载操作符或提供自定义比较函数对象。
方法一：重载 operator>，配合 greater方法二：定义仿函数（functor）作为比较器
示例：按成员值排序的节点小根堆
struct Node { int val; Node(int v) : val(v) {}};struct Compare {bool operator()(const Node& a, const Node& b) {return a.val > b.val; // 小根堆：父节点大于子节点时下沉}};
priority_queue<Node, vector, Compare> minHeap;
手写数组版小根堆（适用于算法题）
在某些竞赛或面试场景中，可能需要手动实现堆结构。基本思路是用数组存储完全二叉树，并维护堆性质。
父节点索引：(i - 1) / 2左孩子：2 * i + 1，右孩子：2 * i + 2插入元素后上浮（shift up），删除后下沉（shift down）
关键操作示例（最小堆插入与弹出）：
vector heap;void push(int x) {heap.push_back(x);int i = heap.size() - 1;while (i > 0 && heap[(i-1)/2] > heap[i]) {swap(heap[(i-1)/2], heap[i]);i = (i-1)/2;}}
void pop() {if (heap.empty()) return;heap[0] = heap.back();heap.pop_back();int i = 0;while (true) {int smallest = i;int left = 2i+1, right = 2i+2;if (left < heap.size() && heap[left] < heap[smallest])smallest = left;if (right < heap.size() && heap[right] < heap[smallest])smallest = right;if (smallest == i) break;swap(heap[i], heap[smallest]);i = smallest;}}
基本上就这些。日常开发推荐使用 STL 的 priority_queue 配合 greater，简洁高效。需要更高控制粒度时再考虑手写堆逻辑。
以上就是c++++中如何实现小根堆_c++小根堆实现技巧的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1480100.html
微信扫一扫 
支付宝扫一扫 
