堆的核心算法解析

核心要点

这个精简版堆只保留了最核心的两个算法：

节点索引计算公式（堆的基础）

父节点索引 = (当前索引 - 1) / 2
左子节点索引 = 当前索引 * 2 + 1  
右子节点索引 = 当前索引 * 2 + 2

核心算法1: 上浮调整 (heapifyUp)

用途: 插入新元素后维护堆性质 原理: 新元素从末尾开始，与父节点比较，如果优先级更高就向上交换

插入流程:
1. 将新元素添加到数组末尾
2. 从末尾位置开始向上调整
3. 与父节点比较，满足条件就交换
4. 重复直到堆性质满足或到达根节点

核心算法2: 下沉调整 (heapifyDown)

用途: 删除堆顶后维护堆性质 原理: 从堆顶开始，与子节点比较，让优先级最高的节点上浮

删除流程:
1. 保存堆顶元素(要返回的值)
2. 用最后一个元素替换堆顶
3. 删除最后一个元素
4. 从堆顶开始向下调整
5. 在父子三个节点中找优先级最高的
6. 如果子节点优先级更高就交换
7. 重复直到堆性质满足

算法可视化

插入过程示例

插入序列: 4, 10, 3, 5, 1

插入4:   [4]

插入10:  [4] -> [10,4]
         (10比4大,向上交换)

插入3:   [10,4,3]
         (3比10小,不需要调整)

插入5:   [10,4,3,5] -> [10,5,3,4]  
         (5比4大,向上交换)

插入1:   [10,5,3,4,1]
         (1比4小,不需要调整)

删除过程示例

从 [10,5,3,4,1] 开始删除

删除10:  [10,5,3,4,1] -> [1,5,3,4] -> [5,4,3,1]
         (用1替换10,然后下沉调整)

删除5:   [5,4,3,1] -> [1,4,3] -> [4,1,3]
         (用1替换5,然后下沉调整)

关键理解点

  1. 堆的本质: 完全二叉树，用数组存储，满足堆序性质
  2. 索引关系: 数组下标直接对应树节点位置
  3. 调整方向:
    • 插入→上浮(与父节点比较)
    • 删除→下沉(与子节点比较)
  4. 时间复杂度:
    • 插入: O(log n)
    • 删除: O(log n)
    • 查看堆顶: O(1)

Compare参数说明

  • greater<T>: 最大堆(大的元素优先级高)
  • less<T>: 最小堆(小的元素优先级高)

这就是堆的全部核心！掌握这两个调整算法，就掌握了堆的精髓。