答案：C++中可通过priority_queue或手动实现数组堆来构建大根堆和小根堆。1. priority_queue默认为大根堆，小根堆需使用greater；2. 手动实现时，大根堆通过父节点大于子节点的性质，用shiftUp和shiftDown维护结构，小根堆反之。两种方式均适用于堆排序等场景。
在C++中实现大根堆和小根堆，可以借助标准库中的 priority_queue，也可以手动实现基于数组的堆结构。下面从两种方式出发，介绍如何构建大根堆和小根堆，并结合堆排序的应用说明其使用场景。
使用 priority_queue 实现大根堆和小根堆
C++ 标准库中的 priority_queue 默认是一个大根堆，可以直接使用。若要实现小根堆，需要指定比较函数。
示例代码：
#include #include #include// 大根堆（默认）std::priority_queue max_heap;
// 小根堆（使用 greater）std::priority_queue<int, std::vector, std::greater> min_heap;
// 使用示例max_heap.push(10);max_heap.push(30);max_heap.push(20);
std::cout << "大根堆顶部: " << max_heap.top() << std::endl; // 输出 30
立即学习“C++免费学习笔记（深入）”；
min_heap.push(10);min_heap.push(30);min_heap.push(20);
std::cout << "小根堆顶部: " << min_heap.top() << std::endl; // 输出 10
手动实现堆结构（数组 + 下标操作）
堆本质是一棵完全二叉树，可用数组表示。父节点与子节点的下标关系如下：
父节点下标： (i – 1) / 2左子节点下标： 2 * i + 1右子节点下标： 2 * i + 2
通过 上浮（shift up） 和 下沉（shift down） 操作维护堆性质。
class MaxHeap {private: std::vector heap;void shiftUp(int i) { while (i > 0) { int parent = (i - 1) / 2; if (heap[i] <= heap[parent]) break; std::swap(heap[i], heap[parent]); i = parent; }}void shiftDown(int i) { int n = heap.size(); while (true) { int maxIndex = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap[maxIndex]) maxIndex = left; if (right heap[maxIndex]) maxIndex = right; if (maxIndex == i) break; std::swap(heap[i], heap[maxIndex]); i = maxIndex; }}
public:void push(int val) {heap.push_back(val);shiftUp(heap.size() - 1);}
void pop() { if (heap.empty()) return; std::swap(heap[0], heap.back()); heap.pop_back(); shiftDown(0);}int top() { return heap.empty() ? -1 : heap[0]; }bool empty() { return heap.empty(); }
};
小根堆只需将比较条件反过来即可（如 > 改为
堆排序的基本原理与实现
堆排序利用大根堆的性质，每次将堆顶最大元素移到末尾，然后调整剩余元素为新堆。
步骤：
构建大根堆（从最后一个非叶子节点开始下沉）交换堆顶与堆尾元素缩小堆大小，对新堆顶执行下沉重复直到堆只剩一个元素
void heapify(std::vector& arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2;if (left arr[largest]) largest = left;if (right arr[largest]) largest = right;if (largest != i) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest);}
}
void heapSort(std::vector& arr) {int n = arr.size();
// 构建大根堆for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);// 堆排序for (int i = n - 1; i > 0; i--) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); // 排除已排序部分}
}
堆排序时间复杂度为 O(n log n)，空间复杂度 O(1)，是一种不稳定的排序算法。
基本上就这些。标准库优先队列适合快速开发，手动实现有助于理解底层机制，堆排序在内存受限或需保证最坏情况性能时很有用。
以上就是C++怎么实现一个大根堆和小根堆_C++数据结构与堆排序应用的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1489567.html
微信扫一扫 
支付宝扫一扫 
