小 K. 同学

堆 #

• 堆结构就是用数组实现的 完全二叉树结构

  js

  数组 [5, 3, 6, 2, 4, 1] 表示的完全二叉树为：
          5
      3        6
  2      4  1
  
  // 在数组结构表示的完全二叉树中，
  // 获取某节点父节点的位置为：
  ~~((i - 1) / 2) // ~~: 取整，对正数相当于 Math.floor，对负数相当于 Math.ceil
  // i 为当前子节点的索引
  // 某节点左子节点下标为：
  2 * i + 1
  // 某节点右子节点下标为：
  2 * (i + 1)
  

• 完全二叉树中如果每棵子树的最大值都在顶部就是 大根堆

  js

  // 例如：
  const arr = [6, 4, 5, 2, 3, 4, 0]
          6
      4        5
  2      3  4     0
  

• 完全二叉树中如果每棵子树的最小值都在顶部就是 小根堆

• 堆结构的 heapInsert 与 heapify 操作

  heapInsert：判定插入节点和父节点的大小，将二叉树更新为大根堆

  ts

  function heapInsert(arr: number[], idx: number) {
    // 当父节点数值大于子节点数值，交换两个数
    while (arr[idx] > arr[(idx - 1) >> 1]) {
      const sonIdx = (idx - 1) >> 1
      swap(arr, idx, sonIdx)
      idx = sonIdx
    }
  }
  

• 堆结构的增大和减少

• 优先级队列结构就是堆结构