堆 (Binary Heap)
完全二叉树，用数组存储。分为大顶堆（parent >= child）和小顶堆（parent <= child）。堆顶为最值。
结构定义
typedef struct {
int *data;
size_t size;
size_t capacity;
} Heap;
索引关系（0-indexed 数组）
parent(i) = (i - 1) / 2
left(i) = 2 * i + 1
right(i) = 2 * i + 2
函数签名（小顶堆）
| 函数 | 复杂度 | 说明 |
|---|
void heap_init(Heap *h, size_t cap) | O(1) | 初始化 |
void heap_push(Heap *h, int val) | O(log n) | 插入，上浮 |
int heap_pop(Heap *h) | O(log n) | 弹出堆顶，下沉 |
int heap_top(Heap *h) | O(1) | 查看堆顶 |
void heap_heapify(int *arr, size_t n) | O(n) | 批量建堆 |
int heap_empty(Heap *h) | O(1) | 判空 |
void heap_free(Heap *h) | O(1) | 释放 |
上浮与下沉
/* 上浮：新元素插入末尾，逐级与父节点比较交换 */
static void sift_up(Heap *h, size_t i) {
while (i > 0) {
size_t p = (i - 1) / 2;
if (h->data[p] <= h->data[i]) break;
swap(&h->data[p], &h->data[i]);
i = p;
}
}
/* 下沉：堆顶替换后，逐级与较小子节点交换 */
static void sift_down(Heap *h, size_t i) {
while (1) {
size_t smallest = i;
size_t l = 2 * i + 1, r = 2 * i + 2;
if (l < h->size && h->data[l] < h->data[smallest]) smallest = l;
if (r < h->size && h->data[r] < h->data[smallest]) smallest = r;
if (smallest == i) break;
swap(&h->data[i], &h->data[smallest]);
i = smallest;
}
}
典型应用
| 应用 | 使用的堆类型 | 说明 |
|---|
| 优先队列 | 小顶堆/大顶堆 | heap_push + heap_pop |
| 堆排序 | 大顶堆 | 建堆 + 反复弹出 |
| Top-K 问题 | 小顶堆（size=K） | 维护 K 个最大元素 |
| Dijkstra 最短路径 | 小顶堆 | 获取最小距离节点 |
| 合并 K 个有序链表 | 小顶堆 | 每次取最小值 |
跨语言参考