c++中如何实现小根堆_c++小根堆实现技巧-C++-PHP中文网

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

尼克

发布： 2025-10-21 12:53:01

原创

948人浏览过

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

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

在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;

登录后复制

}

自定义结构体的小根堆

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

有道小P

有道小P，新一代AI全科学习助手，在学习中遇到任何问题都可以问我。

查看详情

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

以上就是c++++中如何实现小根堆_c++小根堆实现技巧的详细内容，更多请关注php中文网其它相关文章！