小顶堆

• 完全二叉树：

  • 一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为 i（1≤i≤n）的结点与满二叉树中编号为 i 的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树
  • 一棵深度为 k 且有个结点的二叉树称为满二叉树
  • 叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部
  • 如果完全二叉树缺少节点，那一定在右侧

• 小顶堆：

  • 必须是一个完全二叉树(满足二叉树的所有的性质)
  • 任何子树中必须满足父元素小于任何子元素的值

• 需要实现的方法：

  • peek(): T | boolean 查询堆顶的数据，但是不修改数据
  • poll(): T | boolean 从堆顶弹出一个元素，调整结构(堆尾元素添加到堆顶，并且开始下调整)
  • offer(value: T): boolean 从堆底添加一个元素，调整结构(上调整)
  • isEmpty(): boolean 判断堆是否为空
  • size(): number 返回堆的长度

• 实现案例

  • 求最值 场景使用最多(比如：获取前 5 个最大值)