堆
二叉堆
堆（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)
最大堆删除
-
用最后一个节点覆盖根节点
-
删除最后一个节点
-
循环执行以下操作（图中的 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 操作
