C++怎么实现一个堆(Heap)_C++数据结构与优先队列(priority_queue)

C++中堆是基于完全二叉树的结构，用于实现优先队列。1. STL的priority_queue默认为最大堆，提供push、top、pop等操作；2. 手动实现需掌握shiftUp和shiftDown以维护堆序性；3. 堆适用于优先队列、Top K问题、堆排序和Dijkstra算法；4. 注意priority_queue不支持遍历，手动实现时防止数组越界，自定义类型需重载比较规则。

在C++中，堆（Heap）是一种基于完全二叉树的数据结构，常用于实现优先队列。堆分为最大堆（大根堆）和最小堆（小根堆），其中最大堆的父节点值不小于子节点，最小堆则相反。C++标准库提供了 priority_queue 来方便使用堆，但理解手动实现堆有助于掌握其底层原理。

1. 使用 STL 的 priority_queue 实现堆

C++ 标准库中的 priority_queue 默认实现的是最大堆，基于 vector 和堆算法自动维护堆序性。

基本用法：

• priority_queue max_heap;：创建最大堆
• priority_queue, greater> min_heap;：创建最小堆
• push(x)：插入元素
• top()：获取堆顶元素
• pop()：删除堆顶元素
• empty() 和 size()：判断是否为空和获取大小

示例代码：

#include 
#include 
using namespace std;
int main() {
priority_queue max_heap;
max_heap.push(10);
max_heap.push(30);
max_heap.push(20);
while (!max_heap.empty()) {
    cout << max_heap.top() << " ";
    max_heap.pop();
}
// 输出：30 20 10
return 0;
}

2. 手动实现最大堆
手动实现堆可以加深对上浮（shift up）和下沉（shift down）操作的理解。通常使用数组存储完全二叉树。
关键操作：


插入（push）：将元素添加到末尾，然后执行上浮操作维护堆性质

删除堆顶（pop）：将最后一个元素移到堆顶，然后执行下沉操作

上浮（shiftUp）：比较当前节点与父节点，若大于父节点则交换

下沉（shiftDown）：比较父节点与两个子节点，与较大者交换直到满足堆性质

简单实现示例：
#include 
#include 
using namespace std;
class MaxHeap {
private:
vector heap;
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 < n) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int maxIndex = index;

        if (left < n && heap[left] > heap[maxIndex])
            maxIndex = left;
        if (right < n && heap[right] > heap[maxIndex])
            maxIndex = right;

        if (maxIndex == index) break;
        swap(heap[index], heap[maxIndex]);
        index = maxIndex;
    }
}
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() {
    return heap.empty() ? -1 : heap[0];
}

bool empty() {
    return heap.empty();
}

int size() {
    return heap.size();
}
};

这个类实现了基本的最大堆功能，可用于替代 priority_queue 理解内部机制。
3. 堆的应用场景
堆常用于以下场景：


优先队列：任务调度、事件处理等需要按优先级出队的场合

求 Top K 元素：例如找出最大或最小的 K 个数，使用大小为 K 的堆效率高

堆排序：时间复杂度 O(n log n)，原地排序

Dijkstra 算法：结合最小堆可高效提取最短路径节点

例如，找数组中最大的 K 个数，可以用最小堆维护 K 个元素，遍历过程中只保留较大的值。
4. 注意事项
使用堆时需要注意：

STL 的 priority_queue 不支持遍历和删除非堆顶元素
手动实现时注意数组越界，特别是左右子节点索引计算
自定义类型需重载比较函数或提供仿函数
堆的插入和删除时间复杂度为 O(log n)，建堆过程可优化至 O(n)

基本上就这些。掌握 priority_queue 的使用和堆的手动实现，能更好应对算法题和实际开发中的优先级管理需求。堆的核心在于维护堆序性，理解 shiftUp 和 shiftDown 是关键。
 
		


# ai 
# c++ 
# ios 
# stream 
# 标准库 
# int 
# void 
# 数据结构 
# 堆 
# public 
# 事件 
# 算法 
# 大堆 
# 遍历 
# 自定义 
# 不支持 
# 二叉树 
# 的是 
# 是一种 
# 可以用 
# 适用于 
 




相关文章：
如何获取上海专业网站定制建站电话？ 
建站之星图片链接生成指南：自助建站与智能设计教程 
 大连 网站制作,大连天途有线官网？ 
常州自助建站工具推荐：低成本搭建与模板选择技巧 
宝塔新建站点为何无法访问？如何排查？ 
香港服务器网站测试全流程：性能评估、SEO加载与移动适配优化 
如何在VPS电脑上快速搭建网站？ 
 长春网站建设制作公司,长春的网络公司怎么样主要是能做网站的？ 
 想学网站制作怎么学,建立一个网站要花费多少？ 
 微信h5制作网站有哪些,免费微信H5页面制作工具？ 
 测试制作网站有哪些,测试性取向的权威测试或者网站？ 
如何快速生成凡客建站的专业级图册？ 
 网站制作哪家好,cc、.co、.cm哪个域名更适合做网站？ 
建站之星如何防范黑客攻击与数据泄露？ 
如何在阿里云虚拟机上搭建网站？步骤解析与避坑指南 
香港服务器网站卡顿？如何解决网络延迟与负载问题？ 
建站VPS推荐：2025年高性能服务器配置指南 
 盐城做公司网站,江苏电子版退休证办理流程？ 
rsync同步时出现rsync: failed to set times on “xxxx”: Operation not permitted 
建站之星下载版如何获取与安装？ 
 python的本地网站制作,如何创建本地站点？ 
C++如何使用std::optional？（处理可选值） 
如何使用Golang安装API文档生成工具_快速生成接口文档 
 湖南网站制作公司,湖南上善若水科技有限公司做什么的？ 
如何基于PHP生成高效IDC网络公司建站源码？ 
建站之星后台管理如何实现高效配置？ 
 网站制作专业公司有哪些,如何制作一个企业网站，建设网站的基本步骤有哪些？ 
 免费公司网站制作软件,如何申请免费主页空间做自己的网站？ 
如何用腾讯建站主机快速创建免费网站？ 
阿里云网站搭建费用解析：服务器价格与建站成本优化指南 
 设计网站制作公司有哪些,制作网页教程？ 
建站之星各版本价格是多少？ 
javascript中的try catch异常捕获机制用法分析 
 活动邀请函制作网站有哪些,活动邀请函文案？ 
实例解析Array和String方法 
香港服务器如何优化才能显著提升网站加载速度？ 
如何选择域名并搭建高效网站？ 
香港服务器选型指南：免备案配置与高效建站方案解析 
如何通过西部数码建站助手快速创建专业网站？ 
如何有效防御Web建站篡改攻击？ 
建站之星24小时客服电话如何获取？ 
如何确认建站备案号应放置的具体位置？ 
 手机网站制作与建设方案,手机网站如何建设？ 
建站主机空间推荐  高性价比配置与快速部署方案解析 
如何通过网站建站时间优化SEO与用户体验？ 
韩国服务器如何优化跨境访问实现高效连接？ 
如何通过建站之星自助学习解决操作问题？ 
 北京网站制作网页,网站升级改版需要多久？ 
黑客如何利用漏洞与弱口令入侵网站服务器？ 
如何通过二级域名建站提升品牌影响力？