堆(Heap)

作者: 张_何 | 来源:发表于2021-09-26 15:38 被阅读0次

堆Heap
heap (堆)
Heap 堆
堆：Heap
堆 (Heap)
堆（Heap）
堆（heap）
堆 - Heap
堆（heap）
堆-Heap

堆

堆也是一种树状的数据结构,常见的堆实现有:
- 二叉堆(Binary Heap, 完全二叉堆)
- 多叉堆(D-heap、D-ary Heap)
- 索引堆(Index Heap)
- 二项堆(Binomial Heap)
- 斐波那契堆(Fibonacci Heap)
- 左倾堆(Leftist Heap, 左式堆)
- 斜堆(Skew Heap)
堆的一个重要性质: 任意节点的值总是≥或≤子节点的值
- 如果任意节点的值总是≥子节点的值,称为:最大堆、大顶堆、大根堆
- 如果任意节点的值总是≤子节点的值,称为:最小堆、小根堆、小顶堆
由此可见堆中的元素必须具备可比较性

堆的基本接口设计

int size();
boolean isEmpty();
void clear();
void add(E element); // 添加元素
E get(); // 获得堆顶元素
E remove(); // 删除堆顶元素
E replace(E element); // 删除堆顶元素的同时插入一个新元素

二叉堆(Binary Heap)

二叉堆的逻辑结构就是一颗完全二叉树,所以也叫完全二叉堆
鉴于完全二叉树的一些性质,二叉堆的底层(物理结构)一般用数组实现既可
索引 i 的规律(n 是元素数量)
- 如果 i = 0, 它是根节点
- 如果 i = 0, 它的父节点的索引为 floor((i-1)/2)
- 如果2i + 1 ≤ n - 1, 它的左子节点的索引为 2i + 1
- 如果 2i + 1 ＞ n - 1, 它无左子节点
- 如果 2i + 2 ≤ n - 1, 它的右子节点的索引为 2i + 2
- 如果 2i + 2 ＞ n - 1, 它无右子节点

最大堆的添加

循环执行一下操作:
- 如果node > 父节点, 与父节点交换位置
- 如果 node ≤ 父节点,或者 node 没有父节点, 退出循环
这个过程叫上滤(Sift Up), 时间复杂度为 $O(log)n$
上滤优化: 一般交换位置需要 3 行代码,可以进一步优化,将新添加节点备份,确定最终位置才摆放上去

最大堆删除

用最后一个节点覆盖根节点
删除最后一个节点
循环执行以下操作:
- 如果 node < 最大的子节点,与最大的子节点交换位置
- 如果 node ≥ 最大的子节点,或者 node 没有子节点,退出循环
这个过程叫做下滤,时间复杂度 $O(logn)$
同样的,交换位置的操作可以像添加那样进行优化

最大堆-批量建堆

批量建堆有两种做法:
- 自上而下的上滤
- 自下而上的下滤

批量建堆效率对比

所有节点的深度之和
- 仅仅是叶子节点,就有近 n / 2 个,而且每一个叶子节点的深度都是 $O(logn)$ 级别的
- 因此,在叶子节点这一块,就达到了 $O(nlogn)$ 级别
- $O(nlogn)$ 的时间复杂度足以利用排序算法对所有节点进行全排序
所有节点的高度之和
- 假设是满树,节点总个数为 n,树高为 h, 那么 n = 2^h - 1
- 所有节点的树高之和 H(n) = 2⁰ * (h - 0) + 2¹ * (h - 1) + 2² * (h - 2) + ... + 2^h-1 * [h - (h - 1)]
- H(n) = h * (2⁰ + 2¹ + 2² + ... +2^h-1) - [1 * 2¹ + 2 * 2² + 3 * 2³ + ... + (h-1)*2^h-1]
- H(n) = h * (2^h - 1) - [(h - 2) * 2^h + 2]
- H(n) = h * 2^h - h - h * 2^h + 2^h+1 - 2
- H(n) = 2^h+1 - h -2 = 2 * (2^h - 1) -h = 2n - h = 2n - log₂(n+1) = $O(n)$
公式推导

S(h) = 1 * 2¹ + 2 * 2² + 3 * 2³ + ... + (h -2) * 2^h-2 + (h - 1) * 2^h-1
2S(h) = 1 * 2² + 2 * 2³ + 3 * 2⁴ + ... + (h -2) * 2^h-1 + (h - 1) * 2^h
S(h) - 2S(h) = [2¹ + 2² + 2³ + ... + 2^h-1] - (h-1) * 2^h = (2^h - 2) - (h - 1) * 2^h
S(h) = (h - 1) * 2^h - (2^h - 2) = (h-2)*2^h + 2

为什么自上而下的上滤和自下而上的下滤可以批量建堆成功,而自上而下的下滤和自下而上的上滤不行呢?
其原因是不论是自上而下的上滤还是自下而上的下滤,每次操作后都保证的局部是大顶堆或小顶堆,而自上而下的下滤和自下而上的上滤不行

Top K 问题

从 n 个整数中,找出最大前 k 个数(k 远远小于 n)
如果使用排序算法进行全排序,需要的时间复杂度来解决
- 新建一个小顶堆
- 扫描 n 个整数
  先将遍历到的前 k 个数放入堆中
  从第k + 1 个数开始,如果大于堆顶元素,就使用 replace 操作(删除堆顶元素,将第 k + 1 个数添加到堆中)
- 扫描完毕后,堆中剩下的就是最大的前 k 个数
如果是找出最小的前 k 个数呢?
- 用大顶堆
- 如果小于堆顶元素,就使用 replace 操作