数据结构详解:堆、哈希表与字符串哈希
堆 (Heap)
堆是一种特殊的完全二叉树。除了最后一层节点外,其余层节点均非空,且最后一层节点从左到右依次排列。
- 小根堆:任意节点的值均小于或等于其子节点的值。
- 大根堆:任意节点的值均大于或等于其子节点的值。
本文以小根堆为例,介绍堆的手写实现及核心操作。
堆的存储
完全二叉树通常使用一维数组进行顺序存储。若根节点下标为 1,则对于任意节点 u:
- 左子节点下标为
2 * u - 右子节点下标为
2 * u + 1 - 父节点下标为
u / 2
堆的基本操作
堆的维护主要依赖两个核心操作:down(u) 和 up(u)。
1. down(u) 操作
将节点 u 向下调整,使其满足堆的性质。比较当前节点与其左右子节点,若子节点更小,则交换并继续向下递归。
void down(int u) {
int t = u;
if (u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t) {
swap(h[u], h[t]);
down(t);
}
}
2. up(u) 操作
将节点 u 向上调整。若当前节点小于父节点,则交换并继续向上。
void up(int u) {
while (u / 2 && h[u / 2] > h[u]) {
swap(h[u / 2], h[u]);
u /= 2;
}
}


