目录
1.二叉树的顺序存储
1.1存储方式:
1.2下标的关系:
2.堆(优先级队列)
2.1堆的概念
2.2堆的操作-向下调整
2.3堆的操作-建堆
2.4堆的操作-入队列
2.5堆的操作-出队列
1.二叉树的顺序存储
1.1存储方式:
使用数组保存二叉树结构,其方式就是将二叉树用层序遍历的方式存入数组当中,一般只适合表示
完全二叉树,因为非完全二叉树会有空间浪费的现象;而堆在逻辑上就是一颗完全二叉树,堆也正是保
存在数组当中的,所以堆的保存方式就是将堆进行层序遍历然后存储在数组当中.
1.2下标的关系:
已知父亲节点(parent)的下标;则有
左孩子(left)的下标=2*parent+1;
右孩子(right)的下标=2*parent+2;
已知孩子节点(child)(不区分左右)的下标;则有
父亲节点(parent)下标=(child-1)/2;
2.堆(优先级队列)
2.1堆的概念
- 堆逻辑上是一棵完全二叉树
- 堆物理上是保存在数组当中
- 满足任意节点的值都大于其子树中节点的值,叫大根堆
- 满足任意节点的值都小于其子树中节点的值,叫小根堆
- 堆的基本作用是,快速找到集合中的最值
2.2堆的操作-向下调整
- 堆逻辑上是一棵完全二叉树
- 堆物理上是保存在数组当中
- 满足任意节点的值都大于其子树中节点的值,叫大根堆
- 满足任意节点的值都小于其子树中节点的值,叫小根堆
- 堆的基本作用是,快速找到集合中的最值
2.2堆的操作-向下调整
前提:左右子树必须已经是一个堆,才能进行向下调整
说明： 1. array 代表存储堆的数组
2. size 代表数组中被视为堆数据的个数
3. index 代表要调整位置的下标
4. left 代表 index 左孩子下标
5. right 代表 index 右孩子下标
6. min 代表 index 的最小值孩子的下标
向下调整的过程(以小堆为例):
1.index如果已经是叶子节点,则整个调整过程结束
1.1 判断index位置有没有孩子
1.2 因为堆是完全二叉树,若没有左孩子就一定没有右孩子,
所以只需判断是否有左孩子
1.3 因为堆的存储结构是数组,所以判断是否有左孩子的时候,
就等于判断左孩子对应的下标是否越界
2.确定left 或right,谁是index的最小孩子min
2.1 如果右孩子不存在,则min=left
2.2 比较 array[left] 和 array[right] 值的大小,选择小的为min
3.比较array[index] 和 array[min] 的值,如果 array[index] <= array[min],则满足
小根堆的要求,调整结束
4.否则,交换 array[index] 和 array[min] 的值
5.因为min位置的堆的性质可能会被破坏,所以把min当作index,向下重复以上过程
以下是图解:
代码:
2.3堆的操作-建堆
建堆:从倒数的第一个非叶子节点的子树开始调整，一直 调整到根节点的树，就可以调整
成堆。
以下为建立大根堆为例:代码如下:
2.4堆的操作-入队列
过程（以大堆为例）：
1. 首先按尾插方式放入数组
2. 比较其和其父亲节点的值的大小，如果父亲节点的值大，则满足堆的性质，插入结束 3. 否则，交换其和父亲节点位置的值，重新进行 2、3 步骤 4. 直到根结点
代码:
图示:
2.5堆的操作-出队列
为了防止破坏堆的结构，删除时并不是直接将堆顶元素删除，而是用数组的最后一个元素替换堆顶元素，然后通过向 下调整方式重新调整成堆.
代码:
希望以上内容对您理解优先级队列有所帮助喔!
