数据结构学习笔记 - 堆和堆排序

我不是女神ヾ 2022-11-04 13:24 138阅读 0赞

## 堆和堆排序 ##

### 简介 ###

堆, 是一种特殊的树  
经典的应用场景, 堆排序, 原地的时间复杂度为O(nlogn)的排序算法  
堆的两点定义:

*  堆是一个完全二叉树
 *  堆中每一个节点的值都必须大于等于/小于等于其子树中每个节点的值

每个节点的值都大于等于子树中每个节点值的堆叫做大顶堆, 反之叫做小顶堆

### 实现一个堆 ###

之前说过完全二叉树适合用数组存储, 所以堆也用数组存储  
堆的核心操作有**插入元素**和**删除堆顶元素**, 以大顶堆为例

1.  插入元素(todo)  
    把新插入的元素放到堆的最后, 并进行调整使其重新满足堆的特性的过程, 叫**堆化(heapify)**  
    堆化有两种, 从下往上和从上往下  
    堆化非常简单, 就是顺着节点所在路径, 向上或者向下, 对比, 然后交换
2.  删除堆顶元素(todo)  
    为保证删除完还是一个完全二叉树, 把最后一个节点放到堆顶,  
    然后利用同样的父子节点对比法, 对不满足父子节点大小关系的互换两个节点, 直到父子节点满足大小关系为止, 这就是从上往下的堆化

一个包含n个节点的完全二叉树, 树的高度不会超过logn, 堆化的过程是顺着节点所在路径比较交换, 所以堆化的时间复杂度跟树的高度成正比, 也就是O(logn)  
插入数据和删除堆顶元素的主要逻辑就是堆化, 所以时间复杂度也是O(logn)

### 堆排序 ###

借助堆这种数据结构实现的排序算法, 叫做堆排序  
时间复杂度非常稳定, 是O(nlogn), 并且是原地排序  
堆排序的过程大致分为两个大步骤, **建堆**和**排序**

1.  建堆  
    建堆有两种思路:  
    第一种, 借助插入元素的思路, 从下标2开始依次插入到堆中, 从前往后处理数据, 每个数据从下往上堆化, 代码示例(todo)  
    第二种, 和第一种相反, 从后往前处理数组, 每个数据从上往下堆化, 代码示例(todo)
2.  排序  
    建堆结束后, 数组中的数据已经是按照大顶堆的特性来组织的, 第一个元素就是堆顶, 也是最大的元素  
    然后采用类似删除堆顶元素的操作, 把堆顶元素和最后一个元素交换, 再堆化剩下n-1个元素, 然后重复交换, 堆化, 交换, 堆化…  
    直到最后堆中只剩下一个元素, 排序工作就完成了, 代码示例(todo)

整个排序过程中, 只需要极个别临时存储空间, 所以堆排序是原地排序算法  
堆排序包括建堆和排序两个操作, 建堆过程时间复杂度O(n), 排序过程时间复杂度O(nlogn), 所以堆排序整体时间复杂度是O(nlogn)  
堆排序不是稳定的排序算法, 因为排序过程中存在最后节点和堆顶节点交换操作, 可能会改变相同值的顺序

### 堆排序和快排 ###

为什么快排比堆排序性能好

1.  堆排序数据访问方式是跳着访问, 对cpu缓存不友好, 快排数据是顺序访问
2.  对于同样数据, 堆排序的数据交换次数比快排多, 建堆会打乱数据原有相对顺序

### 堆的应用 ###

1.  **优先级队列**  
    在优先级队列中, 优先级最高的最先出队, 用堆来实现是最直接, 最高效的  
    往优先级队列插入元素等于往堆中插入一个元素, 从优先级队列取出优先级最高元素, 等于取出堆顶元素  
    优先级队列应用场景非常多, 比如赫夫曼编码, 图的最短路径, 最小生成树算法等
2.  **求Top K**  
    可以维护一个大小为k的小顶堆, 遍历数据, 依次和堆顶元素比较, 如果比堆顶元素大, 就把堆顶元素删除, 将新元素插入堆中  
    如果比堆顶元素小, 就不作处理继续遍历, 等数据遍历完, 堆中就是前k大的数据
3.  **求中位数**  
    对于静态数据, 中位数是固定的, 可以先排序, 第n/2个数据就是中位数, 但对于动态数据集合, 每次排序效率就很低  
    所以借助堆这种数据结构, 不用排序就可以非常高效的实现求中位数操作  
    我们维护两个堆, 前半部分数据存储一个大顶堆, 后半部分数据存储一个小顶堆, 且小顶堆中的数据都大于大顶堆中的数据  
    这样, 大顶堆的堆顶元素就是我们要的中位数  
    每当新添加数据, 如果数据小于等于大顶堆的堆顶, 就插入到大顶堆, 反之插入到小顶堆, 且从这个堆向另一个堆移动数据, 维护两个堆的数据个数的平衡  
    同理, 此方法可计算各个百分位数据, 比如80百分位数, 99百分位数等