c++中如何实现大根堆_c++大根堆实现方法-C++-PHP中文网

c++中如何实现大根堆_c++大根堆实现方法

下次还敢

发布： 2025-10-03 10:10:02

原创

507人浏览过

C++中实现大根堆常用priority_queue或手动数组实现。优先队列默认为最大堆，使用简单；手动实现通过shiftUp和shiftDown维护堆性质，灵活性高；还可使用make_heap等算法操作容器。

c++中如何实现大根堆_c++大根堆实现方法

在C++中实现大根堆（最大堆）有多种方式，最常用的是利用标准库中的 priority_queue，也可以手动使用数组和算法实现一个堆结构。下面分别介绍这两种方法。

1. 使用 priority_queue 实现大根堆

C++ STL 中的 priority_queue 默认就是一个大根堆，可以直接使用。

头文件：#include <queue>
默认情况下，priority_queue 是基于 vector 的最大堆

示例代码：

#include <iostream>
#include <queue>
using namespace std;
<p>int main() {
priority_queue<int> maxHeap;</p><pre class='brush:php;toolbar:false;'>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

手动实现代码示例：

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

#include <iostream>
#include <vector>
using namespace std;
<p>class MaxHeap {
private:
vector<int> heap;</p><pre class='brush:php;toolbar:false;'>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 < n && heap[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++ 还提供了 <algorithm> 中的堆操作函数：

make_heap：将一个区间构造成堆
push_heap：将新元素加入堆
pop_heap：将堆顶移到末尾

示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
<p>int main() {
vector<int> v = {10, 30, 20, 5};
make_heap(v.begin(), v.end());  // 构建大根堆</p><pre class='brush:php;toolbar:false;'>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++大根堆实现方法的详细内容，更多请关注php中文网其它相关文章！