22二叉堆、堆排序

二叉堆、堆排序

二叉堆

堆是基于完全二叉树的数据结构

堆分为大顶堆和小顶堆

大顶堆：根节点值大于孩子

小顶堆：根节点值小于孩子

实现结构：数组

结点的父节点：arr[(x-1)/2]

左孩子：arr[2*x+1]

右孩子：arr[2*x+2]

堆化处理

删除根节点的操作

步骤：

1.找最后一个元素替换根节点，删除这个叶子结点

2.一直将这个与左右子树比较，与较小的交换，直到这个元素到达叶子结点

更新操作

反向堆化处理

步骤：

1.将结点存储的值更新

2.将这个元素与父节点比较，小于父节点就交换，直到不满足条件（没有父结点或大于父结点）

插入操作

插入到末尾结点，进行反向堆化处理，与更新操作一致

堆排序

进行堆化操作

应用场景

优先级队列

队列中的每一个元素都具有优先级，优先级高的先出队，优先级相同的按照顺序依次出队

案例

1.线程

2.迪杰斯特拉算法或者普林姆算法的优化

基本步骤

1.初始化结点（将结点路径值设为最大，源点为0）

2.定义一个优先级队列，队列中的元素记录结点的编号和最短路径值

3.遍历队顶结点的邻接结点，如果找到一个小于当前最短路径，更新最短路径并将这个结点入队