c++中如何实现小根堆_c++小根堆实现技巧

C++中实现小根堆常用STL的priority_queue，通过greater或自定义比较器实现，默认为大根堆。示例：priority_queue minHeap; 支持基本类型与结构体，后者需重载operator>或定义仿函数。竞赛中可手写数组版堆，用vector模拟完全二叉树，实现上浮插入与下沉删除。日常推荐STL方式，简洁高效；特殊需求再考虑手动实现。

在C++中实现小根堆，最常用的方式是利用标准模板库（STL）中的 priority_queue，并结合自定义比较方式。默认情况下，priority_queue 实现的是大根堆，但通过调整比较器可以轻松转换为小根堆。

使用 priority_queue 实现小根堆

要让 priority_queue 变成小根堆，只需传入 greater 作为第三个模板参数。

示例代码：

#include 
#include 
#include 
#include 
using namespace std;
立即学习“C++免费学习笔记（深入）”；
int main() {
priority_queue, greater> minHeap;
minHeap.push(10);
minHeap.push(5);
minHeap.push(15);

while (!minHeap.empty()) {
    cout << minHeap.top() << " ";
    minHeap.pop();
}
// 输出：5 10 15
return 0;
}

自定义结构体的小根堆
如果需要对结构体或类类型建小根堆，可以通过重载操作符或提供自定义比较函数对象。

							

								
								

									知识吐司
									
专注K12教育的AI知识漫画生成工具
								
								下载 
							
						

方法一：重载 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, 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，简洁高效。需要更高控制粒度时再考虑手写堆逻辑。