最大堆基础概念

最大堆是一种基于完全二叉树的数据结构，具有以下关键特性：

核心性质

1. 结构特性：最大堆是一棵完全二叉树，即除最后一层外，其他层节点全满，且最后一层节点尽可能靠左排列。
2. 堆序特性：每个父节点的值大于或等于其子节点的值。因此，根节点是堆中的最大值。

存储方式

• 数组表示：利用数组高效存储完全二叉树，父子节点关系通过下标计算：
  • 父节点位置 i 的左子节点：2i + 1
  • 父节点位置 i 的右子节点：2i + 2
  • 子节点位置 i 的父节点：⌊(i-1)/2⌋

基本操作

1. 插入元素（上浮）：

   • 将新元素添加到数组末尾。
   • 上浮调整：若新元素值大于父节点，则与父节点交换，递归直至满足堆序。
   • 时间复杂度：O(log n)。

2. 删除最大值（下沉）：

   • 取出根节点（最大值），将数组末尾元素移至根位置。
   • 下沉调整：比较当前节点与左右子节点，若小于子节点，则与最大子节点交换，递归直至满足堆序。
   • 时间复杂度：O(log n)。

3. 构建堆：

   • 自下而上法：从最后一个非叶子节点（位置 ⌊n/2⌋ - 1）开始，向前遍历所有节点，依次执行下沉操作。
   • 时间复杂度：O(n)（优于逐个插入的 O(n log n)）。

应用场景

1. 堆排序：反复取出堆顶元素（最大值）并调整堆，实现升序排序。
2. 优先队列：高效获取和删除最高优先级元素（如任务调度）。

示例分析

以数组 [3, 5, 1, 8, 2] 构建最大堆：

1. 定位非叶子节点：最后一个非叶子节点为索引 1（元素 5）。
2. 调整子树：
   • 索引 1（5）的子树无需调整（子节点 8 和 2 均小于 5）。
   • 调整索引 0（3）：
     • 与左子节点 5 交换 → [5, 3, 1, 8, 2]
     • 交换后索引 1（3）的子树需调整，与子节点 8 交换 → [5, 8, 1, 3, 2]
   • 最终根节点 5 仍小于左子 8，交换根 → [8, 5, 1, 3, 2]，满足最大堆。

复杂度总结

最大堆通过高效维护元素的偏序关系，在动态数据管理和排序任务中表现卓越。