详细介绍堆（Heap）这一核心数据结构。涵盖其定义（完全二叉树 + 堆序性）、存储方式（数组映射）、核心操作（上浮/下沉/建堆）及时间复杂度分析。通过 C++ 模板实现展示大根堆与小根堆逻辑，并深入讲解堆排序、优先队列、TopK 问题及中位数查询等经典应用场景。最后对比堆与 BST 区别，总结优缺点及常见误区，帮助读者掌握堆的原理与实战应用。
堆是计算机科学中核心的数据结构之一，基于完全二叉树构建，兼具高效的插入、删除和极值查询能力，广泛应用于优先队列、堆排序、TopK 问题等场景。
堆是一种完全二叉树（Complete Binary Tree），同时满足堆序性（Heap Property）。完全二叉树的定义是：除最后一层外，每一层的节点数均为最大值，且最后一层的节点从左到右连续排列（无空洞）。这种结构决定了堆可以用数组高效存储，无需额外指针开销。
堆序性是堆与普通完全二叉树的核心区别，分为两种类型：
parent.val ≥ left.val && parent.val ≥ right.val），堆顶（根节点）是整个堆的最大值。parent.val ≤ left.val && parent.val ≤ right.val），堆顶是整个堆的最小值。堆和 BST 常被混淆，但核心目标完全不同：
| 特性 | 堆（大根堆/小根堆） | 二叉搜索树（BST） |
|---|---|---|
| 结构要求 | 完全二叉树 | 任意二叉树（通常平衡化） |
| 有序性 | 仅父子节点满足堆序（全局无序） | 左子树 < 根 < 右子树（全局有序） |
| 核心操作效率 | 插入/删除堆顶 O(logn)，查极值 O(1) | 插入/删除/查找 O(logn)（平衡 BST） |
| 适用场景 | 优先队列、TopK、堆排序 | 动态查找、有序遍历 |
由于堆是完全二叉树，无空洞节点，因此数组是堆的最优存储方式，无需额外空间存储指针。数组与二叉树节点的映射关系如下：
假设堆的数组为 vector<T> heap，对于索引为 i 的节点（从 0 开始计数）：
parent = (i - 1) / 2（整数除法，自动向下取整）left = 2 * i + 1right = 2 * i + 2示例：小根堆 [2, 5, 3, 8, 7, 6] 对应的完全二叉树结构：
2 (i=0)
/ \
5(i=1) 3(i=2)
/ \ /
8(i=3) 7(i=4) 6(i=5)
验证映射关系：i=1 的父节点是 (1-1)/2=0，i=2 的左子节点是 2*2+1=5，完全符合数组存储逻辑。
堆的所有功能基于两个核心操作：上浮（Sift Up） 和 下沉（Sift Down）。下面实现一个支持大根堆/小根堆的通用模板类 Heap<T, Compare>，其中 Compare 是比较函数对象（默认大根堆）。
#include <vector>
#include <algorithm>
#include <stdexcept>
// 比较函数对象：大根堆（默认）
template<typename T>
struct MaxHeapCompare {
bool operator()(const T& a, const T& b) const {
return a < b; // 父节点需大于子节点，故 a<b 时需交换
}
};
// 比较函数对象：小根堆
template<typename T>
struct MinHeapCompare {
bool operator()(const T& a, const T& b) const {
return a > b; // 父节点需小于子节点，故 a>b 时需交换
}
};
// 堆模板类：T 为元素类型，Compare 为比较规则
template<typename T, typename Compare = MaxHeapCompare<T>>
class Heap {
private:
std::vector<T> data; // 存储堆的数组
Compare cmp; // 比较函数对象
// 上浮操作：从索引 i 向上调整堆
void siftUp(int i) {
while (i > 0) {
int parent = (i - 1) / 2;
if (!cmp(data[parent], data[i])) break;
std::swap(data[parent], data[i]);
i = parent;
}
}
// 下沉操作：从索引 i 向下调整堆
void siftDown(int i) {
int n = data.size();
while (true) {
int maxChild = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && cmp(data[maxChild], data[left])) maxChild = left;
if (right < n && cmp(data[maxChild], data[right])) maxChild = right;
if (maxChild == i) break;
std::swap(data[i], data[maxChild]);
i = maxChild;
}
}
public:
Heap() = default;
Heap(const std::vector<T>& arr) : data(arr) {
buildHeap();
}
void buildHeap() {
int n = data.size();
int lastNonLeaf = (n - 2) / 2;
for (int i = lastNonLeaf; i >= 0; --i) {
siftDown(i);
}
}
void push(const T& val) {
data.push_back(val);
siftUp(data.size() - 1);
}
void pop() {
if (empty()) throw std::runtime_error("Heap is empty, cannot pop!");
int n = data.size();
data[0] = data[n - 1];
data.pop_back();
if (!empty()) siftDown(0);
}
const T& top() const {
if (empty()) throw std::runtime_error("Heap is empty, cannot get top!");
return data[0];
}
bool empty() const { return data.empty(); }
size_t size() const { return data.size(); }
};
(n-2)/2，从该节点向左遍历至根，依次执行 siftDown。堆排序利用大根堆（升序）或小根堆（降序）实现排序，时间复杂度 O(nlogn)，空间复杂度 O(1)，但不稳定。
template<typename T>
void heapSort(std::vector<T>& arr) {
int n = arr.size();
if (n <= 1) return;
auto buildMaxHeap = [&](std::vector<T>& a, int size) {
int lastNonLeaf = (size - 2) / 2;
for (int i = lastNonLeaf; i >= 0; --i) {
int parent = i;
while (true) {
int maxChild = parent;
int left = 2 * parent + 1;
int right = 2 * parent + 2;
if (left < size && a[left] > a[maxChild]) maxChild = left;
if (right < size && a[right] > a[maxChild]) maxChild = right;
if (maxChild == parent) break;
std::swap(a[parent], a[maxChild]);
parent = maxChild;
}
}
};
buildMaxHeap(arr, n);
for (int i = n - 1; i > 0; --i) {
std::swap(arr[0], arr[i]);
buildMaxHeap(arr, i);
}
}
优先队列是堆的典型应用，元素按优先级排序。C++ STL 提供 priority_queue，底层基于堆实现。
greater<T>（需包含 <functional>）；#include <queue>
#include <functional>
#include <iostream>
#include <string>
struct Task {
std::string name;
int priority;
Task(std::string n, int p) : name(n), priority(p) {}
};
struct TaskCompare {
bool operator()(const Task& a, const Task& b) const {
return a.priority > b.priority;
}
};
int main() {
std::priority_queue<Task> maxPq;
maxPq.push(Task("任务 A", 3));
maxPq.push(Task("任务 B", 5));
maxPq.push(Task("任务 C", 2));
while (!maxPq.empty()) {
auto task = maxPq.top();
maxPq.pop();
std::cout << "执行：" << task.name << "（优先级：" << task.priority << ")" << std::endl;
}
return 0;
}
使用小根堆可实现 O(nlogK) 时间复杂度、O(K) 空间复杂度。
#include <vector>
#include <queue>
#include <iostream>
std::vector<int> topK(std::vector<int>& data, int k) {
if (data.empty() || k <= 0 || k > data.size()) throw std::invalid_argument("Invalid input!");
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int i = 0; i < k; ++i) minHeap.push(data[i]);
for (int i = k; i < data.size(); ++i) {
if (data[i] > minHeap.top()) {
minHeap.pop();
minHeap.push(data[i]);
}
}
std::vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
return result;
}
使用两个堆（大根堆 + 小根堆）可实现 O(logn) 插入和 O(1) 查询。
#include <vector>
#include <queue>
#include <iostream>
#include <stdexcept>
class MedianFinder {
private:
std::priority_queue<int> leftHeap; // 大根堆
std::priority_queue<int, std::vector<int>, std::greater<int>> rightHeap; // 小根堆
void balance() {
if (leftHeap.size() - rightHeap.size() == 2) {
rightHeap.push(leftHeap.top());
leftHeap.pop();
} else if (rightHeap.size() - leftHeap.size() == 1) {
leftHeap.push(rightHeap.top());
rightHeap.pop();
}
}
public:
MedianFinder() = default;
void addNum(int num) {
if (leftHeap.empty() || num <= leftHeap.top()) {
leftHeap.push(num);
} else {
rightHeap.push(num);
}
balance();
}
double findMedian() {
if (leftHeap.empty() && rightHeap.empty()) throw std::runtime_error("No data!");
if (leftHeap.size() > rightHeap.size()) return leftHeap.top();
return (leftHeap.top() + rightHeap.top()) / 2.0;
}
};
pop() 不返回元素，需先 top() 再 pop()；求和式 $\sum_{k=0}^{h-1} 2^k \times (h - k)$ 是典型的「等差×等比」数列求和，适合用错位相减法求解。
设 $S = \sum_{k=0}^{h-1} 2^k \times (h - k)$，展开得： $S = h \times 2^0 + (h-1) \times 2^1 + \dots + 1 \times 2^{h-1}$
两边乘以 2： $2S = h \times 2^1 + (h-1) \times 2^2 + \dots + 1 \times 2^h$
相减得： $S = 2^{h+1} - h - 2$
对于满二叉树，节点数 $n = 2^h - 1$，故 $2^h = n + 1$，$2^{h+1} = 2n + 2$。
代入得 $S = (2n + 2) - h - 2 = 2n - h$。
因为 $h = \log_2(n+1) \approx \log_2 n$，相对于 $n$ 为低阶项，主导项为 $2n$。
因此，$S = O(n)$。
堆是基于完全二叉树的高效数据结构，核心优势在于 O(1) 极值查询和 O(logn) 插入/删除。掌握堆的关键在于理解'上浮'和'下沉'的维护逻辑，以及建堆的 O(n) 复杂度推导。在实际开发中，优先使用 STL 的 priority_queue，但自定义堆实现能更深入理解其底层原理。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online