1. 优先队列
说堆排序之前，我们要从一种特殊的数据结构——优先队列说起。
优先队列最大的两个特征：插入元素和删除最大元素
优先队列的实现方式有很多种。
我们希望插入元素和删除最大元素的时间复杂度都能降低到最低，比如1。
| 数据结构 | 插入元素 | 删除最大元素 |
|---|---|---|
| 有序数组 | N | 1 |
| 无序数组 | 1 | N |
| 堆 | logN | logN |
| 理想情况 | 1 | 1 |
先说结论：用堆的方式来实现，可以保证插入元素和删除最大元素的时间复杂度都为logN
2. 堆
堆的定义：二叉堆，一种二叉树的结构，又分为大二叉堆和小二叉堆，我们此处主要讲大二叉堆
特点：二叉树的父节点都大于两个子节点，根节点是二叉树中最大的节点。
对于节点a[i]而言，它的父节点为a[(i-1)/2]，它的子节点（如果有的话）为a[2i+1]和a[2i+2]
堆的两种关键算法
有时，我们会发现有些节点不符合二叉堆的规则，那可以使用上浮或者下沉的算法，将元素放到合适的位置上去、
上浮（针对子节点）
上浮算法：找到父节点（a[(k-1)/2]），如果比父节点大，则和父节点交换；完成一次上浮之后，继续和当前的父节点比较，直到比父节点小为止。
代码如下：
private void heap_swim(Comparable[] a, int k) {
while (k > 0 && less(a[(k - 1) / 2], a[k])) {
exchange(a, (k - 1) / 2, k);
k = (k - 1) / 2;
}
}
下沉（针对父节点）
下沉算法：找到子节点（a[2k+1]和a[2k+2]）中比较大的一个，如果比子节点小，则和子节点交换；完成一次下沉后，继续与当前的子节点比较，直到比子节点大为止。
代码如下
private void heap_sink(Comparable[] a, int k, int n) {
while ((2 * k + 1) < n) {
int j = 2 * k + 1;
if ((j < n) && less(a[j], a[j + 1])) {
j = j + 1;
}
if (less(a[k], a[j])) {
exchange(a, k, j);
k = j;
} else {
break;
}
}
}
堆的操作
堆的初始化
堆的初始化有两套方案：
- 顺序从左到右对每个元素进行上浮操作（把每个元素都当成新插入的元素）。由于第1个元素（a[0]）开始并没有根节点，所以，循环可以从第二个元素(a[1])开始
for (int k = 1; k < a.length; k++){
heap_swim(a, k);
}
- 逆序从右往左对每个元素进行下沉操作。由于节点a[(n-1)/2]之后的节点都是子节点，所以循环可以从a[(n-1)/2]开始
for (int k = (n - 1) / 2; k >= 0; k--) {
heap_sink(a, k, n);
}
下沉算法的方案相对循环较少，一般堆的初始化都是采用方案二。
堆插入元素
堆的插入元素过程就是一个元素上浮的过程
堆删除最大元素
堆的删除最大元素分两步：
- 将根节点元素与最后一个子节点元素交换，然后删除最后一个节点，
-
根节点元素下沉
堆排序
前面已经搞清楚了优先队列，又搞清楚了堆的结构，以及堆的上浮和下沉算法。下面我们就来研究堆排序了。
堆排序的步骤：
- 将数组中的数据初始化为二叉堆（一般使用下沉算法来实现）
- 取出二叉堆的根节点并和数组尾节点交换，这样最大值就放到了a[n-1]。
- 现在a[0]不符合二叉堆的规则，使用下沉算法将a[0]的元素放到合适的节点。然后取出最大值放到a[n-2]
- 依次循环2.3步，直到所有二叉堆中所有元素取完。
private void heap_sort(Comparable[] a) {
int n = a.length - 1;
for (int k = (n - 1) / 2; k >= 0; k--) {
heap_sink(a, k, n);
}
while (n > 0) {
exchange(a, 0, n--);
heap_sink(a, 0, n);
}
}
堆排序的时间复杂度：nLgN
参考资料：《算法 第四版》
