c++中实现小根堆常用STL的priority_queue，通过greater<T>或自定义比较器实现，默认为大根堆。示例：priority_queue<int, vector<int>, greater<int>> minHeap; 支持基本类型与结构体，后者需重载operator>或定义仿函数。竞赛中可手写数组版堆，用vector模拟完全二叉树，实现上浮插入与下沉删除。日常推荐STL方式，简洁高效；特殊需求再考虑手动实现。
在C++中实现小根堆，最常用的方式是利用标准模板库（STL）中的 priority_queue，并结合自定义比较方式。默认情况下，priority_queue 实现的是大根堆，但通过调整比较器可以轻松转换为小根堆。
使用 priority_queue 实现小根堆
要让 priority_queue 变成小根堆，只需传入 greater<T> 作为第三个模板参数。
- 包含头文件：
#include <queue>和#include <functional> - 声明格式：
priority_queue<int, vector<int>, greater<int>> minHeap;
示例代码：
#include <iostream> #include <queue> #include <vector> #include <functional> <p>using namespace std;</p><p><span>立即学习</span>“<a href="https://pan.quark.cn/s/6e7abc4abb9f" style="text-decoration: underline !important; color: blue; font-weight: bolder;" rel="nofollow" target="_blank">C++免费学习笔记（深入）</a>”；</p><p>int main() { priority_queue<int, vector<int>, greater<int>> minHeap;</p><pre class="brush:php;toolbar:false;"><pre class="brush:php;toolbar:false;">minHeap.push(10); minHeap.push(5); minHeap.push(15); while (!minHeap.empty()) { cout << minHeap.top() << " "; minHeap.pop(); } // 输出：5 10 15 return 0;
}
自定义结构体的小根堆
如果需要对结构体或类类型建小根堆，可以通过重载操作符或提供自定义比较函数对象。
- 方法一：重载
operator>，配合greater<T> - 方法二：定义仿函数（functor）作为比较器
示例：按成员值排序的节点小根堆
struct node { int val; Node(int v) : val(v) {} }; <p>struct Compare { bool operator()(const Node& a, const Node& b) { return a.val > b.val; // 小根堆：父节点大于子节点时下沉 } };</p><p>priority_queue<Node, vector<Node>, Compare> minHeap;
手写数组版小根堆（适用于算法题）
在某些竞赛或面试场景中，可能需要手动实现堆结构。基本思路是用数组存储完全二叉树，并维护堆性质。
- 父节点索引：
(i - 1) / 2 - 左孩子：
2 * i + 1，右孩子：2 * i + 2 - 插入元素后上浮（shift up），删除后下沉（shift down）
关键操作示例（最小堆插入与弹出）：
vector<int> heap; <p>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; } }</p><p>void pop() { if (heap.empty()) return; heap[0] = heap.back(); heap.pop_back(); int i = 0; while (true) { int smallest = i; int left = 2<em>i+1, right = 2</em>i+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，简洁高效。需要更高控制粒度时再考虑手写堆逻辑。