大顶堆知识梳理

2022-07-26 算法

大顶堆

大顶堆

  • 完全二叉树:

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

    • 必须是一个完全二叉树(满足二叉树的所有的性质)
    • 任何子树中必须满足父元素大于任何子元素的值
  • 需要实现的方法:

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

    • 求最值 场景使用最多(比如:获取前 5 个最小值)
Last Updated: 7/26/2022, 9:39:53 PM
Powered By Valine
v1.5.1