数据结构详解：堆、哈希表与字符串哈希

数据结构详解：堆、哈希表与字符串哈希

堆 (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;
    }
}