今天我们来学习堆和堆排序。
什么是堆
堆是一种特殊的树，满足以下两点要求：
- 堆是一个完全二叉树。
- 堆中每个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
通过要求二可知，堆有两种类型，大顶堆和小顶堆：
- 对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆”。
- 对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆”。
上图中，第1、2个是大顶堆，第3个是小顶堆，第4个不是堆。
如何实现一个堆
首先要知道堆支持哪些操作，以及如何存储。
存储一个堆
完全二叉树比较适合用数组来存储。通过下标即可找到一个节点的左右子节点和父节点。
堆的操作包括两个：往堆中插入一个元素，删除堆顶元素。
往堆中插入一个元素
往堆中插入一个元素的过程是，把新插入的元素放到堆的最后，通过调整，让其重新满足堆的特性，这个过程叫作堆化（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(a, i, i / 2);
i = i / 2;
}
}
private void Swap(int[] a, int x, int y)
{
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}
删除堆顶元素
从堆的定义的第二条中，任何节点的值都大于等于（或小于等于）子树节点的值，可以发现，堆顶元素存储的就是堆中数据的最大值或最小值。
假设堆是大顶堆，删除堆顶元素之后，就要把第二大的元素放到堆顶，如下图
但是这种方法有点问题，就是最后堆化的堆并不满足完全二叉树的特性。
通过从上往下的堆化方法可以解决这个问题，把最后一个节点放到堆顶，然后利用同样的父子节点对比方法，对于不满足父子节点大小关系的，互换两个节点，并且重复这个过程，直到父子节点之间满足大小关系为止。
代码实现如下：
public void RemoveMax()
{
if (count == 0) return;
// 把最右侧子树的叶子节点放到堆顶
a[1] = a[count];
// 去掉最后一个元素
count--;
// 堆化
Heapify(a, n, 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[2 * i + 1]) maxPos = i * 2 + 1;
// 如果最大节点为当前节点，跳出
if (maxPos == i) break;
// 否则交换，并进入下一次循环
Swap(a, i, maxPos);
i = maxPos;
}
}
时间复杂度
一个包含n个节点的完全二叉树，树的高度不会超过log2n。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化，因此时间复杂度是O(logn)。
如何基于堆实现排序
堆排序的过程大致分解为两大步骤：建堆和排序。
建堆
建堆有两种思路：
- 在堆中插入一个元素。从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。
- 与第一种截然相反，从后往前处理数组，并且每个数据都是从上往下堆化。
这里介绍第二种思路。
代码实现如下：
private void BuildHeap(int[] a, int n)
{
// 从下标n/2到1进行堆化
// 因为叶子节点不需要堆化，而堆是完全二叉树，即当前节点i的左节点是2*i，右节点是2*i+1，即最后一个父节点只能是n/2
for (int i = n / 2; i >= 1; i++)
{
Heapify(a, n, i);
}
}
// 自上往下堆化
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[2 * i + 1]) maxPos = i * 2 + 1;
// 如果最大节点为当前节点，跳出
if (maxPos == i) break;
// 否则交换，并进入下一次循环
Swap(a, i, maxPos);
i = maxPos;
}
}
这段代码中，我们对下标从$\frac{n}{2}$开始到1的数据进行堆化，下标从$\frac{n}{2}+1$到n的节点都是叶子节点。
时间复杂度
每个节点堆化的时间复杂度是O(logn)，那$\frac{n}{2}+1$个节点的堆化的总时间复杂度是O(nlogn)。
推导过程
堆化节点从倒数第二层开始。堆化过程中，需要比较和交换的节点个数与这个节点的高度k成正比。
将每个非叶子节点的高度求和，得到下面的公式S1:
这个公式的求解稍微有点技巧，我们把公式左右都乘以2，得到另一个公式S2，再将S2减去S1，就可以得到S了。
S的中间部分是一个等比数列，用等比数列的求和公式来计算，最终的结果就是下图的样子。
因为$h=\log_2 n$，代入公式S，就得到S=O(n)，所以建堆的时间复杂度是O(n)。
排序
建堆后，数组中的数据是大顶堆。把堆顶元素，即最大元素，跟最后一个元素交换，那最大元素就放到了下标为n的位置。
这个过程有点类似上面的“删除堆顶元素”的操作，当堆顶元素移除之后，把下标n的元素放堆顶，然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆。一直重复这个过程，直到最后堆中只剩下下标为1的元素，排序就完成了。
代码实现如下：
// n表示数据的个数，数组a中的数据从下标1到n的位置。
public 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)。
整个堆排序的过程，只需要极个别临时存储空间，所以堆排序是原地排序算法。
堆排序不是稳定的排序算法，因为在排序过程，存在将堆最后一个节点跟堆顶节点互换的操作，所有就有可能改变值相同数据的原始相对顺序。
在实际开发中，为什么快速排序要比堆排序性能好
1.堆排序数据访问的方式没有快速排序友好
快速排序，数据是顺序访问的。堆排序，数据是跳着访问的。对CPU缓存不友好。
2.对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。
快速排序数据交换的次数不会比逆序度多。
堆排序的建堆过程会打造数据的原有顺序，降低有序度，交换次数更多。
整体代码：
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(a, i, i / 2);
i = i / 2;
}
}
public void RemoveMax()
{
if (count == 0) return;
// 把最右侧子树的叶子节点放到堆顶
a[1] = a[count];
// 去掉最后一个元素
count--;
// 堆化
Heapify(a, n, 1);
}
private void BuildHeap(int[] a, int n)
{
// 从下标n/2到1进行堆化
// 因为叶子节点不需要堆化，而堆是完全二叉树，即当前节点i的左节点是2*i，右节点是2*i+1，即最后一个父节点只能是n/2
for (int i = n / 2; i >= 1; i++)
{
Heapify(a, n, i);
}
}
// n表示数据的个数，数组a中的数据从下标1到n的位置。
public void Sort(int[] a, int n)
{
BuildHeap(a, n);
int k = n;
while (k >= 1)
{
Swap(a, 1, k);
--k;
Heapify(a, k, 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[2 * i + 1]) maxPos = i * 2 + 1;
// 如果最大节点为当前节点，跳出
if (maxPos == i) break;
// 否则交换，并进入下一次循环
Swap(a, i, maxPos);
i = maxPos;
}
}
private void Swap(int[] a, int x, int y)
{
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
}
