堆

二叉堆

堆（Heap）也是一种树状的数据结构

堆的性质

1 、堆的一个重要性质：任意节点的值总是 ≥（ ≤ ）子节点的值

如果任意节点的值总是 ≥ 子节点的值，称为：最大堆、大根堆、大顶堆

如果任意节点的值总是 ≤ 子节点的值，称为：最小堆、小根堆、小顶堆

2 、堆中的元素必须具备可比较性（跟二叉搜索树一样）

常见的堆

二叉堆（Binary Heap，完全二叉堆）

多叉堆（D-heap、D-ary Heap）

索引堆（Index Heap）

二项堆（Binomial Heap）

斐波那契堆（Fibonacci Heap）

左倾堆（Leftist Heap，左式堆）

斜堆（Skew Heap）

接口

添加元素

获取最大值

删除最大值

时间复杂度：获取最大值：O(1)、删除最大值：O(logn)、添加元素：O(logn)

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

二叉堆

二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆

鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可

索引 i 的规律（ n 是元素数量）

索引 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(logn)

最大堆删除

1. 用最后一个节点覆盖根节点

2. 删除最后一个节点

3. 循环执行以下操作（图中的 43 简称为 node）

   如果 node < 最大的子节点 。与最大的子节点交换位置

   如果 node ≥ 最大的子节点， 或者 node 没有子节点 。 退出循环

这个过程，叫做下滤（Sift Down），时间复杂度：O(logn)

同样的，交换位置的操作可以像添加那样进行优化

最大堆 – 批量建堆（Heapify）

批量建堆，有 2 种做法

自上而下的上滤

自下而上的下滤

最大堆 – 批量建堆 – 效率对比

Top K问题

从 n 个整数中，找出最大的前 k 个数（ k 远远小于 n ）

如果使用排序算法进行全排序，需要 O(nlogn) 的时间复杂度

如果使用二叉堆来解决，可以使用 O(nlogk) 的时间复杂度来解决

• 新建一个小顶堆
• 扫描 n 个整数 先将遍历到的前 k 个数放入堆中 从第 k + 1 个数开始，如果大于堆顶元素，就使用 replace 操作（删除堆顶元素，将第 k + 1 个数添加到堆中）
• 扫描完毕后，堆中剩下的就是最大的前 k 个数

如果是找出最小的前 k 个数呢？

用大顶堆 如果小于堆顶元素，就使用 replace 操作