答案：C++中可通过priority_queue或手动实现数组堆来构建大根堆和小根堆。1. priority_queue默认为大根堆，小根堆需使用greater<int>；2. 手动实现时，大根堆通过父节点大于子节点的性质，用shiftUp和shiftDown维护结构，小根堆反之。两种方式均适用于堆排序等场景。
在C++中实现大根堆和小根堆，可以借助标准库中的 priority_queue，也可以手动实现基于数组的堆结构。下面从两种方式出发，介绍如何构建大根堆和小根堆，并结合堆排序的应用说明其使用场景。
使用 priority_queue 实现大根堆和小根堆
C++ 标准库中的 priority_queue 默认是一个大根堆，可以直接使用。若要实现小根堆，需要指定比较函数。
示例代码：
#include <queue> #include <vector> #include <iostream> <p>// 大根堆（默认） std::priority_queue<int> max_heap;</p><p>// 小根堆（使用 greater） std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;</p><p>// 使用示例 max_heap.push(10); max_heap.push(30); max_heap.push(20);</p><p>std::cout << "大根堆顶部: " << max_heap.top() << std::endl; // 输出 30</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>min_heap.push(10); min_heap.push(30); min_heap.push(20);</p><p>std::cout << "小根堆顶部: " << min_heap.top() << std::endl; // 输出 10</p>
手动实现堆结构（数组 + 下标操作）
堆本质是一棵完全二叉树，可用数组表示。父节点与子节点的下标关系如下：
- 父节点下标： (i - 1) / 2
- 左子节点下标： 2 * i + 1
- 右子节点下标： 2 * i + 2
通过 上浮（shift up） 和 下沉（shift down） 操作维护堆性质。
class MaxHeap {
private:
std::vector<int> heap;
<pre class='brush:php;toolbar:false;'>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 < n && heap[left] > heap[maxIndex])
maxIndex = left;
if (right < n && heap[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<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
<pre class='brush:php;toolbar:false;'>if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}}
void heapSort(std::vector<int>& 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)，是一种不稳定的排序算法。
基本上就这些。标准库优先队列适合快速开发，手动实现有助于理解底层机制，堆排序在内存受限或需保证最坏情况性能时很有用。
