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()：判断是否为空和获取大小
示例代码：
立即学习“C++免费学习笔记（深入）”；
#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 10return 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 heap[maxIndex]) maxIndex = left; if (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 是关键。
以上就是C++怎么实现一个堆(Heap)_C++数据结构与优先队列(priority_queue)的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1488252.html
微信扫一扫 
支付宝扫一扫 
