堆
堆是一种数据结构，常用于堆排序。
堆的定义：
- 堆是一个完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列
- 堆中每一个节点的值都必须大于等于或小于等于其子树中(左右子节点)每个节点的值
每个节点的值都大于等于其子树中每个节点值的堆叫做大顶堆；每个节点的值都小于等于子树中每个节点值的堆，我们叫做小顶堆。
上图中，第一个和第二个是大顶堆，第三个是小顶堆，最后一个不是堆，不满足完全二叉树条件。
堆的存储
完全二叉树适合用数组存储，因为不需要像链表法一样存储额外的左右指针，更加节省空间，示意图如下：
数组中下标为i的节点的左子节点，就是下标为i*2的节点，右子节点就是下标为i*2+1的节点，父节点就是下标为i/2的节点。
下面的堆是以大顶堆为基础。
往堆中插入一个元素
插入元素到堆中，会导致堆不满足其特性条件，需要进行堆化(heapify)操作使得堆继续满足其两个特性要求，示意图如下：
堆化非常简单，就是顺着节点坐在的路径，向上或者向下，对比，然后交换，分为两种：
- 从下往上
- 从上往下
示意图如下：
代码如下：
public class Heap {
private int[] a; // 数组，从下标 1 开始存储数据
private int n; // 堆可以存储的最大数据个数
private int count; // 堆中已经存储的数据个数
public Heap(int capacity) {
a = new int[capacity + 1];
n = capacity;
count = 0;
}
public void insert(int data) {
if (count >= n) return; // 堆满了
++count;
a[count] = data;
int i = count;
// 自下往上堆化
while (i/2 > 0 && a[i] > a[i/2]) {
// swap() 函数：交换下标为 i 和 i/2 的两个元素
swap(a, i, i/2);
i = i/2;
}
}
}
删除堆顶元素
堆顶元素存储的是堆中数据的最大值或者最小值，对于大顶堆，堆顶元素就是最大的元素；对于小顶堆，堆顶元素就是最小的元素。
删除堆顶元素之后，需要将左右子树中的第二大元素移动到堆顶，依次类推，示意图如下：
但是该方法导致无法满足完全二叉树的条件。换个思路，将最后一个节点放到堆顶，然后利用同样的父子节点对比方法，将不满足条件的两个节点互换，重复这个过程，示意图如下：
因为我们移除的是数组中的最后一个元素，而在堆化的过程中，都是交换操作，不会出现数组中的“空洞”，所以这种方法堆化之后的结果，肯定满足完全二叉树的特性。
代码如下：
public void removeMax() {
if (count == 0) return -1; // 堆中没有数据
a[1] = a[count];
--count;
heapify(a, count, 1);
}
private void heapify(int[] a, int n, int i) { // 自上往下堆化
while (true) {
int maxPos = i;
if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
if (maxPos == i) break;
swap(a, i, maxPos);
i = maxPos;
}
}
由于堆化过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是O(logn)，插入删除数据的主要过程就是堆化，因此，其时间复杂度都是O(logn)。
堆排序
堆排序是一种非常稳定的原地排序算法，时间复杂度是O(nlogn)。堆排序的过程是建堆和排序。
建堆
两种思路：
- 在堆中插入一个元素的思路，假设起初堆中只包含一个元素，然后依次插入剩余元素，即将下标从2到n的数据依次插入到堆中，并且从下往上堆化
- 从后往前处理数组，并且每个数据都是从上往下堆化，因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从第一个非叶子节点开始，依次堆化即可，示意图如下：
代码如下：
private static void buildHeap(int[] a, int n) {
//直接对下标n/2开始到1的数据进行堆化，下标是n/2 + 1到n的节点是叶子节点，不需要堆化
for (int i = n/2; i >= 1; --i) {
heapify(a, n, i);
}
}
private static void heapify(int[] a, int n, int i) {
// 从上往下堆化
while (true) {
int maxPos = i;
if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
if (maxPos == i) break;
swap(a, i, maxPos);
i = maxPos;
}
}
对于完全二叉树来说，下标从n/2+1到n的节点都是叶子节点。
需要堆化的节点从倒数第二层开始，每个节点堆化过程中，需要比较和交换的节点个数，跟这个节点的高度k成正比，建堆时每一层的节点个数和对应的高度如下：
将每个非叶子节点的高度和节点个数的乘积求和，得：
左右乘以2，得到S2，有：
S中间部分等比数列，有：
因为h=log2(n)，带入上面的公式S，得到S=O(n)，即建堆的时间复杂度是O(n)
排序
堆排序的过程：
- 将数组中的第一个元素，即最大的元素，堆顶跟最后一个元素交换，放到下标为n的位置。
- 将数组1到n-1区间的元素进行堆化
- 继续执行步骤1，知道剩下一个元素
示意图如下：
代码如下：
// n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
public static void sort(int[] a, int n) {
buildHeap(a, n);
int k = n;
while (k > 1) {
swap(a, 1, k);
--k;
heapify(a, k, 1);
}
}
堆排序的时间复杂度
堆排序：
- 是原地排序算法
- 包括建堆和排序两个过程，
- 建堆：时间复杂度是O(n)
- 排序：时间复杂度是O(nlogn)
- 堆排序整体的时间复杂度是O(nlogn)
- 不是稳定排序算法，因为在排序过程中，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序
如果数组从0开始存储，节点下标为i，那左子节点的小标是2*i+1，右子节点是2*i+2，父节点的下标就是(i-1)/2。
堆排序 VS 快排
- 对于快速排序来说，数据是顺序访问的，对于堆排序来说，数据是跳着访问的，对于CPU缓存不够友好。
- 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序，建堆过程会打乱数据原有的相对先后顺序，导致元数据的有序度降低。示意图如下：
小结
堆包含插入一个元素和删除堆顶元素，前者把新数据放到数组的最后，然后从下往上堆化；后者把数组中的最后一个元素放到堆顶，然后从上往下堆化，两个操作的时间复杂度都是O(logn)。
待排序包含建堆和排序两个过程，前者从下标n/2到1的节点，依次进行从上到下的堆化操作；后者迭代地将堆顶的元素放到堆的末尾，并将堆的大小减一，然后再堆化，重复直到剩下一个元素，整个数组就有序排列了。
堆的应用
- 优先级队列：优先级队列是按照优先级来确定出队顺序，优先级最高的，最先出队。
- 合并有序小文件：小顶堆
- 高性能定时器：小顶堆
- 利用堆求Top K：小顶堆
- 利用堆求中位数：大顶堆存储前半部分数据+小顶堆存储后半部分数据，示意图如下：
对于动态数组，插入新数据后需要调整两个堆的元素，使其满足如果n是偶数，两个堆中个数都是n/2，如果n是奇数，大顶堆中有n/2+1个数据，小顶堆中有n/2个数据，示意图如下：
同样的思路，可以利用两个堆来快速求解其他百分位的数据，如快速求接口的99%响应时间：
- 大顶堆中存储n*99%个数据，小顶堆中存储n*1%个数据，大顶堆的堆顶数据就是我们要找的99%的时间
- 每次插入新数据的时候，需要判断插入哪个堆中：
- 如果新插入数据比大顶堆的堆顶元素小，就插入大顶堆
- 为了避免一个数介于大顶堆堆顶和小顶堆堆顶之间，直接将不满足上一个条件的数据插入小顶堆
- 插入完成需要调整两个堆的元素，让其保持99:1的比例，即将一个堆中的数据放入另一个堆中，直到满足这个比例
注：本文是《数据结构与算法之美》的读书笔记，配套代码地址GitHub。本文仅限个人学习，请勿用作商业用途，谢谢。
Note: Cover Picture