堆(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), 时间复杂度为
• 上滤优化: 一般交换位置需要 3 行代码,可以进一步优化,将新添加节点备份,确定最终位置才摆放上去

最大堆删除

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

最大堆-批量建堆

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

批量建堆效率对比

• 所有节点的深度之和

  • 仅仅是叶子节点,就有近 n / 2 个,而且每一个叶子节点的深度都是级别的
  • 因此,在叶子节点这一块,就达到了级别
  • 的时间复杂度足以利用排序算法对所有节点进行全排序

• 所有节点的高度之和

  • 假设是满树,节点总个数为 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) =

• 公式推导

• 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 操作

作业

• 了解和实现堆排序
• 使用堆排序将一个无序数组转换成一个升序数组
  • 空间复杂度能否下降至?