最短路
堆排序
一、堆排序
大根堆和小根堆
大根堆（Max Heap）
- 定义：在大根堆中，每个父节点的值都大于或等于其子节点的值。换句话说，堆顶元素（根节点）是堆中最大的元素。
- 特性：
- 完全二叉树：大根堆是一棵完全二叉树，意味着树是满的，除了最后一层可能没有填满的情况下。
- 动态增减：插入新元素时，会将其放在堆的末尾，然后不断上升调整位置（上浮）；删除根节点时，将最后一个元素移动到根节点，然后下沉调整位置。
小根堆（Min Heap）
- 定义：在小根堆中，每个父节点的值都小于或等于其子节点的值。也就是说，堆顶元素是堆中最小的元素。
- 特性：
- 同样是一个完全二叉树。
- 插入和删除操作与大根堆类似，但在小根堆中，维护的是最小值而非最大值。
堆排序
- 堆排序是一种基于比较的排序算法，具有良好的平均和最坏情况时间复杂度 O(nlogn)，并且是一种不稳定的排序算法。
- 根据前面的大根堆和小根堆可以知道堆顶（根节点）为最大（小）值，所以每次取出堆顶的值就是排序后的数组，取n个元素，时间复杂度为O(n)
- 取出堆顶元素后维护堆 => 找出新的最大（小）值放到堆顶，维护的时间复杂度为 O(logn)。
堆排序的流程
新增元素
如果在原有的堆上新增一个数，那么只需要把它添加到堆尾，然后一直和父节点比较交换，维护的时间复杂度为O(logn)。
首先，将新值放置在堆的末尾（作为最后一个叶子节点），接下来，检查新元素的父节点。如果新元素的值大于其父节点的值，就交换它们的位置。这个过程可能会向上移动新元素，直到堆的性质被重新满足（即每个父节点都大于或等于其子节点）。
参考
https://www.cnblogs.com/jingmoxukong/p/4303826.html