什么是二叉堆
二叉堆的本质是一种完全二叉树，它分为两种类型：最大堆和最小堆
最大堆任何一个父节点的值，都大于等于它左右孩子的值，最小堆正好与之相反
[图片上传失败...(image-25a0af-1556461270759)]
二叉树的根节点叫做堆顶
最大堆和最小堆的特点是：最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆中的最小元素
堆的自我调整
对于二叉堆有几种操作
- 插入节点
- 删除节点
- 构建二叉堆
这几种操作都是基于堆的自我调整
我们以最大堆为例，分析下堆的自我调整
插入节点
二叉堆的节点插入位置是完全二叉树的最后一个位置，我们插入一个新节点，值为11。
[图片上传失败...(image-9aa082-1556461270759)]
这时候，我们让节点11和父节点5作比较，如果11大于5，则交换他俩交换位置，称为“上浮”
image
继续用节点11和父节点8进行比较，如果节点11大于节点8，则让节点11继续“上浮”
[图片上传失败...(image-5da876-1556461270759)]
继续比较，最终让节点11上浮到堆顶位置
[图片上传失败...(image-ff3bdc-1556461270759)]
删除节点
二叉树删除节点的过程和插入过程正好相反，它每次都是从堆顶删除，将堆顶的节点与与最后一个节点交换位置
[图片上传失败...(image-9302d2-1556461270759)]
然后将堆顶的节点5和它两个孩子进行比较，显然节点10比较打，让他俩交换位置，称为“下沉”
[图片上传失败...(image-5a328e-1556461270759)]
继续让节点5和它的孩子做比较，显然大的是节点8，让节点5继续下沉
[图片上传失败...(image-9bf116-1556461270759)]
此时就重新构建的二叉树。
构建二叉树
构建二叉树，就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点一次下沉（上浮）
- 构建最大堆：节点大的上浮，小的下沉
- 构建最小堆：节点小的上浮，大的下沉
文章：什么是二叉堆？
网友评论