二叉堆（Binary Heap）的插入、删除和建堆操作 二叉堆是一种特殊的完全二叉树，满足堆序性质（Heap Property）。它通常用于实现优先队列。二叉堆主要分为两种：最大堆和最小堆。最大堆中，父节点的值总是大于或等于其子节点的值；最小堆中，父节点的值总是小于或等于其子节点的值。二叉堆通常用数组来存储，利用完全二叉树的性质，可以方便地通过索引计算父节点和子节点的位置。 下面我将详细讲解二叉堆的三个核心操作：插入、删除和建堆。我们以最大堆为例进行说明。 1. 二叉堆的表示 二叉堆在物理上通常用一个数组来存储。对于数组中的任意一个元素，假设其索引为 i （从0开始），则： 父节点索引： (i-1)/2 左子节点索引： 2*i+1 右子节点索引： 2*i+2 2. 插入操作（Insert） 插入操作的目标是将一个新元素添加到堆中，并保持堆的性质。步骤如下： 步骤1：将新元素添加到堆的末尾 在数组的末尾添加新元素。由于堆是完全二叉树，这对应于在树的最后一层最右边的位置添加一个新节点。 步骤2：向上调整（Heapify Up 或 Sift Up） 新元素可能会破坏堆的性质（例如，在最大堆中，新元素可能比它的父节点大）。为了恢复堆的性质，需要将新元素与它的父节点比较。 如果新元素大于父节点（对于最大堆），则交换它们。 重复这个过程，即新元素不断与新的父节点比较，直到新元素不大于其父节点，或者到达堆的根节点。 例子 ：在最大堆 [70, 50, 40, 45, 30] 中插入元素 60。 将60添加到末尾，得到 [70, 50, 40, 45, 30, 60] 。 60的父节点是30（索引(5-1)/2=2），但30<60，交换，得到 [70, 50, 60, 45, 30, 40] 。 60的父节点是50（索引(2-1)/2=0? 不对，2的父节点是(2-1)/2=0? 注意索引：父节点索引公式是 (i-1)/2。对于索引2的元素60，其父节点索引为 (2-1)/2=0.5 向下取整为0，即元素70。60<70，停止。实际上，在第二步中，我们比较的是索引5的元素60的父节点是索引2的元素30。交换后，60的索引变为2。然后，60的新父节点是索引0的元素70。因为60<70，所以停止。最终堆为 [70, 50, 60, 45, 30, 40] 。 时间复杂度 ：由于堆是完全二叉树，树的高度为 O(log n)，所以插入操作的时间复杂度为 O(log n)。 3. 删除操作（Delete） 通常删除操作指的是删除堆顶元素（即最大或最小元素）。步骤如下： 步骤1：用最后一个元素替换堆顶元素 将堆的最后一个元素移动到堆顶（即数组的第一个位置），并删除最后一个元素（减小堆的大小）。这可能会破坏堆的性质。 步骤2：向下调整（Heapify Down 或 Sift Down） 从新的堆顶开始，将其与两个子节点中较大的那个（对于最大堆）比较。 如果堆顶元素小于较大的子节点，则交换它们。 重复这个过程，即当前节点不断与新的子节点比较，直到当前节点大于等于其子节点，或者到达叶子节点。 例子 ：从最大堆 [70, 50, 60, 45, 30, 40] 中删除堆顶元素70。 用最后一个元素40替换堆顶，得到 [40, 50, 60, 45, 30] 。 向下调整：40的子节点是50和60，较大的子节点是60。因为40<60，交换40和60，得到 [60, 50, 40, 45, 30] 。 40的新子节点是45和30（如果存在，这里索引2的左子节点索引为5，但数组只有5个元素，所以40是叶子节点？实际上，索引2的元素40，其左子节点索引为5，超出范围，所以停止。最终堆为 [60, 50, 40, 45, 30] 。 时间复杂度 ：同样，树的高度为 O(log n)，所以删除操作的时间复杂度为 O(log n)。 4. 建堆操作（Heapify） 建堆是指将一个无序的数组调整成一个堆。有两种方法：一种是不断调用插入操作，另一种是更高效的“自底向上”的调整方法。这里讲解效率更高的自底向上建堆。 步骤1：从最后一个非叶子节点开始 最后一个非叶子节点的索引是 n/2 - 1 （其中n是数组长度）。这是因为完全二叉树中，叶子节点没有子节点，不需要向下调整。 步骤2：对每个非叶子节点进行向下调整 从最后一个非叶子节点开始，向前遍历到根节点，对每个节点调用向下调整（Heapify Down）操作。这样可以保证以当前节点为根的子树满足堆的性质。 原理 ：由于向下调整操作能够保证一个节点及其子树满足堆性质，从最后一个非叶子节点开始调整，可以逐步将整个树调整为堆。 例子 ：将数组 [3, 9, 2, 1, 4, 5] 建成最大堆。 数组长度 n=6，最后一个非叶子节点索引为 6/2 - 1 = 2（即元素2）。 对索引2的元素2进行向下调整：2的子节点是5（左子节点索引5）和？右子节点索引6超出范围，所以只有左子节点5。2<5，交换，得到 [3, 9, 5, 1, 4, 2] 。 对索引1的元素9进行向下调整：9的子节点是1和4，9大于它们，无需调整。 对索引0的元素3进行向下调整：3的子节点是9和5，较大的子节点是9。3<9，交换，得到 [9, 3, 5, 1, 4, 2] 。 然后对索引1的新元素3进行向下调整：3的子节点是1和4，较大的子节点是4。3<4，交换，得到 [9, 4, 5, 1, 3, 2] 。现在索引1的元素4，其子节点1和3，无需调整。最终得到最大堆 [9, 4, 5, 1, 3, 2] 。 时间复杂度 ：直观上，每个节点调整的代价与节点的高度成正比。可以证明，建堆的总时间复杂度为 O(n)，而不是 O(n log n)。这是因为大部分节点的高度都很小。 总结 插入 ：添加元素到末尾，然后向上调整。 删除 （堆顶）：用末尾元素替换堆顶，然后向下调整。 建堆 ：从最后一个非叶子节点开始，自底向上进行向下调整。 这些操作保证了二叉堆可以在 O(log n) 时间内完成插入和删除，并在 O(n) 时间内构建堆。二叉堆是实现优先队列的经典数据结构，广泛应用于堆排序、Dijkstra算法、Prim算法等算法中。