二叉堆（Binary Heap）的原理与操作

二叉堆是一种特殊的完全二叉树，它满足堆属性：每个节点的值都大于等于（最大堆）或小于等于（最小堆）其子节点的值。二叉堆通常用数组实现，是优先队列（Priority Queue）的常用底层数据结构。

一、二叉堆的结构与数组表示

1. 完全二叉树性质：

   • 二叉堆是一棵完全二叉树，意味着除了最后一层，其他层都是满的，并且最后一层的节点都尽可能靠左排列。
   • 这个性质使得我们可以用一维数组来高效地表示堆，无需使用指针。

2. 数组索引规则：

   • 根节点存储在索引0（有些实现从索引1开始，这里以0为例）。
   • 对于任意节点i：
     • 其父节点索引：parent(i) = (i - 1) // 2（整数除法）
     • 左子节点索引：left_child(i) = 2*i + 1
     • 右子节点索引：right_child(i) = 2*i + 2

3. 堆属性：

   • 最大堆：array[parent(i)] >= array[i]
   • 最小堆：array[parent(i)] <= array[i]

二、堆的基本操作

1. 插入操作（Insert）：

   • 步骤1：将新元素添加到堆的末尾（即数组的最后一个位置），以保持完全二叉树形态。
   • 步骤2：执行“上浮”（Sift Up / Swim Up）操作，调整新元素的位置以满足堆属性。
     • 比较新节点与其父节点的值。
     • 如果违反堆属性（例如在最大堆中，新节点值大于父节点），则交换两者。
     • 重复此过程，直到新节点到达根位置或满足堆属性为止。
   • 时间复杂度：O(log n)，因为上浮路径的长度等于树的高度。

2. 删除堆顶（Extract-Max/Min）：

   • 步骤1：取出堆顶元素（即数组的第一个元素），它是最大堆中的最大值或最小堆中的最小值。
   • 步骤2：将堆的最后一个元素移动到根位置，以维持完全二叉树结构。
   • 步骤3：执行“下沉”（Sift Down / Heapify）操作，调整根元素的位置。
     • 比较当前节点与其左右子节点（在最大堆中，找出最大的子节点）。
     • 如果当前节点值小于子节点值，则交换两者。
     • 重复此过程，直到当前节点大于等于其子节点或成为叶子节点。
   • 时间复杂度：O(log n)，因为下沉路径的长度最多为树的高度。

三、堆的构建（Heap Construction）

1. 自顶向下构建（逐个插入）：

   • 从一个空堆开始，依次插入每个元素。
   • 每次插入需要O(log n)时间，n个元素总时间复杂度为O(n log n)。
   • 这种方法简单但效率不是最优。

2. 自底向上构建（Heapify）：

   • 将任意数组视为完全二叉树，从最后一个非叶子节点开始，向前遍历到根节点。
   • 对每个节点执行下沉操作，确保以其为根的子树满足堆属性。
   • 最后一个非叶子节点的索引是(n // 2) - 1（n为数组长度）。
   • 时间复杂度分析：虽然每个下沉操作是O(log n)，但整体复杂度可通过数学证明为O(n)，更高效。

四、堆排序（Heap Sort）

堆排序利用最大堆进行升序排序：

1. 构建最大堆（自底向上Heapify）。
2. 重复以下步骤直到堆为空：
   • 将堆顶元素（当前最大值）与堆末尾元素交换。
   • 堆大小减一，对新的根节点执行下沉操作以恢复堆属性。
3. 时间复杂度：O(n log n)，空间复杂度O(1)。

五、优先队列的应用

二叉堆是实现优先队列的理想结构：

• 插入元素：O(log n)
• 获取最高优先级元素：O(1)
• 删除最高优先级元素：O(log n)
• 应用场景：任务调度、Dijkstra算法、哈夫曼编码等。

通过以上步骤，您应该能理解二叉堆的核心原理、操作细节及其应用。重点掌握数组索引的映射关系、上浮/下沉操作的过程，以及不同构建方法的时间复杂度差异。