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

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

1. 二叉堆的结构特性

• 完全二叉树：除了最后一层，其他层节点全满，且最后一层节点靠左排列
• 堆属性：父节点值 ≥ 子节点值（最大堆）或父节点值 ≤ 子节点值（最小堆）
• 数组表示：利用完全二叉树特性，可以用数组紧凑存储（节省指针空间）
  • 对于位置i的节点：
    • 父节点：floor((i-1)/2)
    • 左子节点：2i+1
    • 右子节点：2i+2

2. 核心操作：上浮（Heapify Up）
当某个节点值大于其父节点时（最大堆），需要向上调整：

1. 比较当前节点与父节点的值
2. 如果违反堆属性，交换两者位置
3. 重复过程直到满足堆属性或到达根节点
   时间复杂度：O(log n)，因为最多需要比较树的高度次

3. 核心操作：下沉（Heapify Down）
当某个节点值小于其子节点时（最大堆），需要向下调整：

1. 比较当前节点与其左右子节点的值
2. 找出值最大的子节点
3. 如果子节点值大于当前节点，交换两者位置
4. 重复过程直到满足堆属性或成为叶子节点
   时间复杂度：O(log n)

4. 插入操作详细步骤

1. 将新元素添加到堆的末尾（数组最后位置）
2. 对新元素执行上浮操作：
   • 比较新元素与其父节点的值
   • 如果新元素值更大（最大堆），与父节点交换
   • 重复此过程直到堆属性满足
3. 示例：在最大堆[10,7,8,5,6]中插入9
   • 添加后：[10,7,8,5,6,9]
   • 比较9与其父节点8：9>8，交换→[10,7,9,5,6,8]
   • 比较9与其父节点10：9<10，停止

5. 删除堆顶操作详细步骤

1. 用最后一个元素替换堆顶元素
2. 删除最后一个元素（原堆顶）
3. 对新的堆顶元素执行下沉操作：
   • 比较该元素与其左右子节点
   • 与值更大的子节点交换
   • 重复直到堆属性满足
4. 示例：从最大堆[10,7,9,5,6,8]删除堆顶
   • 用最后元素8替换堆顶：[8,7,9,5,6]
   • 8与子节点比较：左7右9，9最大且9>8，交换→[9,7,8,5,6]
   • 8与子节点比较：无子节点，停止

6. 建堆操作（Heap Construction）
从无序数组构建堆有两种方法：

• 自顶向下：重复调用插入操作，时间复杂度O(n log n)
• 自底向上：从最后一个非叶子节点开始向前遍历，对每个节点执行下沉操作
  • 最后一个非叶子节点位置：floor(n/2)-1
  • 时间复杂度：O(n)，因为大部分节点在底层，下沉操作次数少

7. 堆排序原理

1. 构建最大堆
2. 重复以下步骤直到堆为空：
   • 将堆顶元素（最大值）与最后一个元素交换
   • 堆大小减1
   • 对新的堆顶执行下沉操作
3. 最终得到升序排列的数组

二叉堆通过巧妙利用完全二叉树的数组表示和简单的上浮/下沉操作，实现了高效的插入、删除和建堆操作，是优先队列和堆排序算法的基础数据结构。