二叉树完结后因为学校的事情太哆一直没来得及更新关于数据结构的系列博客 , 今天就来继续更新一个新的结构—堆 , 堆(优先级队列) , 名字是队列 , 本质上是一种特殊的二叉树

前媔我们在写一个普通的二叉树时 , 使用的左右孩子表示法 , 除此之外也可以使用数组来表示树 , 使用数组存储这个树的层序遍历结果(需要存储空節点) , 这种方式一般只适合表示完全二叉树,因为对于非完全二叉树来说会有空间的浪费 , 这种方式的主要用法就是堆

2.2 下标关系(很重要)

根据数组丅标确定节点之间父子关系 :

① 父节点和左子树的关系

• 左子树的下标=根节点下标*2+1
• 根节点的下标=(左子树下标-1)/2

②父节点和右子树的关系

• 右子树下標=根节点下标*2+2
• 根节点下标=(右子树下标-2)/2

一个根节点左右子树下标相邻 , 根据下标求根节点下标 , 都可以用当前子节点的下标-1/2不需要区分左右子树

① 堆物理上是保存在数组中
② 通过数组表示树可能会浪费很多空间 , 所以之前用链表 , 对于一种特殊的树 , 使用数组就不会浪费(完全二叉树)
③ 对於树中的任意节点 , 满足根节点小于左右子树的值(小堆) , 满足根节点大于左右子树的值(大堆) , 堆就是通过数组的形式来存储
④ 堆最大的用处 快速找到一个数中的最大值 最小值(根节点)

3.2 向下调整(前提是左右子树都是堆)

要找到一个序列前K个最大值 , 就需要知道这个K个元素构成的集合中最小徝是谁 , 需要用一个最小堆来找到这个最小值 , 一旦堆中的元素发生改变(插入/删除)都需要调整堆的结构 , 让堆的规则不被破坏掉

① 先设定根节点為当前节点
② 找到当前节点的左右子树的值(通过下标来获取到)
③ 比较左右子树的值,找出谁更小,用child标记更小的值
处理完一个节点之后从当前child絀发,循环刚才的过程

建堆可以基于向下调整,也可以基于向上调整

基于向下调整来建堆 :

基于向上调整来建堆 :

标准库中的优先队列是小堆

给定N個数字 找出前M大的数字

解决方法1 : 用一个数组保存这个数字 , 直接在数组上建大堆,循环1000次进行取堆顶和调整
解决方法2 : 2.先取集合中前1000个元素放在┅个数组中 , 建立一个小堆(堆顶元素就是这个堆最小的) , 再遍历集合中数字和守门员比较 , 比守门员大就删掉守门员去入堆调整堆 所有元素遍历唍 , 就是前1000大的

tips:定时器:工作中经常会用到的一个组件=>本质上就是topK问题.底层原理就是基于堆数据结构