堆

定义

说白了，堆实际上就是一种数据结构，是一棵特殊的完全二叉树。相对于普通的完全二叉树而言，堆的特殊之处在于，其任意一个结点都比它的孩子结点大（此时称为大顶堆），或者都比孩子结点小（此时称为小顶堆）。

初始建堆

如何构建一个堆？事实上，建立堆的过程，就是将一棵完全二叉树调整为堆的过程。不失一般性，接下来我们都以大顶堆为例进行说明。

要想得到这种“任意根结点比孩子结点大”的结构，我们需要按照根结点自底向上、自右向左的顺序，对该根结点所在的子树进行调整。比如下图展示的完全二叉树，我们现在将其调整为大顶堆。

1. 按照自底向上、自右向左的顺序，首先需要检查叶子结点，但是叶子结点没有孩子，因此它们必然满足要求；

2. 比较“4-1”子树，根结点4确实大于孩子结点1，满足要求；

3. 见上图紫色框部分，显然不满足要求，需要对其进行调整：选取两个孩子结点中较大者8，将其与根结点3进行交换，使其满足要求；

   

4. 接下来“25-20-12”满足要求，但是“6-8-4”不满足，同样对其进行调整为“8-6-4”；

   

5. 此时“6-7-3”不满足了，需要再次进行调整，一旦调整完成，以8为根结点的子树就是一个堆了；

6. 接下来检查“18-8-25”，发现同样也需要进行调整，调整为“25-8-25”；

   .svg)

7. 此时往下检查确保以25为根结点的子树构成堆，因此调整右子树“18-20-12”为“20-18-12”，调整完毕后，堆的建立就完成了。

   .svg)

最终建立好的堆结构如下：

调整子树为堆

通过上面的实例分析可以发现：

1. 根结点的扫描是自底向上、自右向左的；
2. 获取到根结点之后，对其所在子树的调整是自上而下的；

究其原因，是因为每一次对父子结点对进行检查时，至多交换一次，也就是说，至多会改变左子树、右子树中一棵子树的根，进而改变这棵子树的结构而导致它有可能不再满足堆的特性。因此需要进一步对这棵子树进行调整，不断地以此类推，就是一个自顶向下的迭代过程。我们把这个过程用代码实现出来，根结点不妨用结点索引from表示。

void downAdjust(int from, int to) {
    // 对[from, to]范围内的结点进行调整，to通常是完全二叉树的最后一个结点索引
    int i = from, j = 2 * from; // 记录根结点以及其左孩子
    while(j <= to) {
        // 左孩子存在
        if(j + 1 <= to && heap[j+1] > heap[j]) {
            // 右孩子也存在且右孩子大于左孩子
            j = j + 1;
        }
        if(heap[j] > heap[i]) {
            // j记录的是左右孩子中的较大者索引，将其与父亲结点交换
            swap(heap[i], heap[j]);
            // 接下来需要对与父亲结点进行交换的孩子结点（即索引j）所在子树进行调整
            i = j;
            j = 2 * i;
        } else	break; // 满足堆的性质，无需任何调整
    }
}

建堆

接下来实现第一条“根结点的扫描是自底向上、自右向左的”，即可完成建堆。在结点数量为$n$的完全二叉树中，叶子结点数量为$\displaystyle \lceil \frac{n}{2} \rceil$，因此范围在$\displaystyle \left[1, \lfloor \frac{n}{2} \rfloor\right]$的结点均为非叶子结点。我们倒着遍历进行调整即可。

void createHeap(int n) {
    int i;
    for(i=n/2; i; i--) {
        downAdjust(i, n);
    }
}

堆排序

回到上面的建堆过程分析中来。显然，每次建立好堆之后，完全二叉树中的最大结点正是根结点，换言之，我们选出了最大结点。那么我们是不是就可以通过每次将完全二叉树调整为堆，得到最大结点，然后将其与完全二叉树中乱序部分的最后一个元素互换，这样不断地从剩余乱序元素中选出最大值放到后面，从而完成排序呢？

图解

我们以一个具体的例子来说明堆排序的过程。首先初始的乱序序列为[25, 8, 20, 7, 4, 18, 12, 6, 3, 14]，我们需要将其按非递减顺序排序。

1. 第一步需要将完全二叉树建成堆，事实上初始情况正是上一部分建堆的结果，已经是堆结构了，因此可以跳过；

2. 此时根结点就是待排序部分的最大元素，于是将其与待排序部分的末位元素互换，最后一个元素位置固定了，待排序序列长度减一，见下图；

   

3. 接下来对$[1,n-1]$范围内的结点调整为大顶堆，以选出最大结点，调整后的结构见下图；

   

4. 同2，将根结点与待排序部分末位元素互换，见下图；

   

5. 同3，对$[1,n-2]$范围内的结点调整为大顶堆，以选出最大结点，调整后的结构见下图；

   

6. 以此类推，接下来每一步给出选出最大结点并重新调整为堆的结果图；

   

7. 

8. 

9. 

10. 

11. 

12. 

13. 此时只剩下一个元素，排序也就完成了。

上述过程便是堆排序的完整可视化排序过程。

代码实现

在理解并实现了自上而下调整为堆的过程和函数downAdjust()后，堆排序的实现也就迎刃而解了。

void heapSort(int n) {
    createHeap(n); // 初始建堆
    int i;
    for(i=n; i>1; i--) {
        // 每次选出当前堆顶最大结点与未排序部分末位元素i互换（而导致有序），故未排序末位元素索引变为i-1
        swap(heap[1], heap[i]);
        downAdjust(1, i-1);
    }
}

总结

分析到这里，我们可以发现，事实上，堆排序的本质是一个“选择排序”——只不过相比于朴素的选择排序，堆排序借助了树形结构的堆来选出当前元素的最大者/最小者，以提高效率。由于每次调整的时间复杂度为$\mathcal{O}(\log n)$，而需要进行$n-1$次调整，故堆排序的时间复杂度为$\mathcal{O}(n\log n)$。

再看看它的空间复杂度，堆排序基本上没有借助额外的存储空间，因此空间复杂度为$\mathcal{O}(1)$。

最后看看它的稳定性。堆排序是不稳定的，因为本质上堆排序属于“选择排序”，且调整堆结构时，父子结点之间会进行换位。正是这种换位，会破坏排序算法的稳定性。

完整代码

void downAdjust(int from, int to) {
    // 对[from, to]范围内的结点进行调整，to通常是完全二叉树的最后一个结点索引
    int i = from, j = 2 * from; // 记录根结点以及其左孩子
    while(j <= to) {
        // 左孩子存在
        if(j + 1 <= to && heap[j+1] > heap[j]) {
            // 右孩子也存在且右孩子大于左孩子
            j = j + 1;
        }
        if(heap[j] > heap[i]) {
            // j记录的是左右孩子中的较大者索引，将其与父亲结点交换
            swap(heap[i], heap[j]);
            // 接下来需要对与父亲结点进行交换的孩子结点（即索引j）所在子树进行调整
            i = j;
            j = 2 * i;
        } else	break; // 满足堆的性质，无需任何调整
    }
}

void createHeap(int n) {
    // 建立堆
    int i;
    for(i=n/2; i; i--) {
        downAdjust(i, n);
    }
}

void heapSort(int n) {
    // 堆排序
    createHeap(n); // 初始建堆
    int i;
    for(i=n; i>1; i--) {
        // 每次选出当前堆顶最大结点与未排序部分末位元素i互换（而导致有序），故未排序末位元素索引变为i-1
        swap(heap[1], heap[i]);
        downAdjust(1, i-1);
    }
}