共计 573 个字符,预计需要花费 2 分钟才能阅读完成。
什么是二叉堆
二叉堆的本质是一种完全二叉树,它分为两种类型:最大堆和最小堆
最大堆任何一个父节点的值,都大于等于它左右孩子的值,最小堆正好与之相反
二叉树的根节点叫做堆顶
最大堆和最小堆的特点是:最大堆的堆顶是整个堆中的最大元素,最小堆的堆顶是整个堆中的最小元素
堆的自我调整
对于二叉堆有几种操作
插入节点
删除节点
构建二叉堆
这几种操作都是基于堆的自我调整
我们以最大堆为例,分析下堆的自我调整
插入节点
二叉堆的节点插入位置是完全二叉树的最后一个位置,我们插入一个新节点,值为 11。
这时候,我们让节点 11 和父节点 5 作比较,如果 11 大于 5,则交换他俩交换位置,称为“上浮”
继续用节点 11 和父节点 8 进行比较,如果节点 11 大于节点 8,则让节点 11 继续“上浮”
继续比较,最终让节点 11 上浮到堆顶位置
删除节点
二叉树删除节点的过程和插入过程正好相反,它每次都是从堆顶删除,将堆顶的节点与与最后一个节点交换位置
然后将堆顶的节点 5 和它两个孩子进行比较,显然节点 10 比较打,让他俩交换位置,称为“下沉”
继续让节点 5 和它的孩子做比较,显然大的是节点 8,让节点 5 继续下沉
此时就重新构建的二叉树。
构建二叉树
构建二叉树,就是把一个无序的完全二叉树调整为二叉堆,本质上就是让所有非叶子节点一次下沉(上浮)
构建最大堆:节点大的上浮,小的下沉
构建最小堆:节点小的上浮,大的下沉
文章:什么是二叉堆?
正文完
发表至: javascript
2018-09-03