堆排序

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. 顺序从左到右对每个元素进行上浮操作（把每个元素都当成新插入的元素）。由于第1个元素（a[0]）开始并没有根节点，所以，循环可以从第二个元素(a[1])开始

for (int k = 1; k < a.length; k++){
    heap_swim(a, k);
}

2. 逆序从右往左对每个元素进行下沉操作。由于节点a[(n-1)/2]之后的节点都是子节点，所以循环可以从a[(n-1)/2]开始

for (int k = (n - 1) / 2; k >= 0; k--) {
    heap_sink(a, k, n);
}

下沉算法的方案相对循环较少，一般堆的初始化都是采用方案二。

堆插入元素

堆的插入元素过程就是一个元素上浮的过程

堆删除最大元素

堆的删除最大元素分两步：

1. 将根节点元素与最后一个子节点元素交换，然后删除最后一个节点，

2. 根节点元素下沉

   
   

堆排序

前面已经搞清楚了优先队列，又搞清楚了堆的结构，以及堆的上浮和下沉算法。下面我们就来研究堆排序了。

堆排序的步骤：

1. 将数组中的数据初始化为二叉堆（一般使用下沉算法来实现）
2. 取出二叉堆的根节点并和数组尾节点交换，这样最大值就放到了a[n-1]。
3. 现在a[0]不符合二叉堆的规则，使用下沉算法将a[0]的元素放到合适的节点。然后取出最大值放到a[n-2]
4. 依次循环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

参考资料：《算法 第四版》