[数据结构与算法]内部排序——堆排序

堆

堆是一棵特殊的完全二叉树，分为小顶堆和大顶堆。小顶堆就是每个节点的值都小于等于其左右子节点的值，所以对于一个小顶堆，其根节点是整棵树的最小值。相应的大顶堆，就是每个节点的值都大于等于其左右子节点的值。

堆排序

以小顶堆为例，利用堆的特性（每个节点的值小于等于其左右子节点的值）就可以对一个数组进行排序。

首先，堆是一棵完全二叉树，所以我们需要将一个数组建成完全二叉树。对于一棵树，我们需要的是能够获得每个节点的父节点及其左右子节点，而对于一棵完全二叉树，将一个数组从下标为 1 开始存储，这样之后可以发现，节点 i 的左子节点的下标为 2 * i， 右子节点的下标为 2 * i + 1。因此，我们只需要从 1 开始存储，就可以轻松获得每个节点的父节点或左右子节点，相当于我们已经建好一棵完全二叉树了。

其次，我们需要将一棵完全二叉树进行调整，使其成为小顶堆。以最简单的完全二叉树为例，取一棵由三个节点构成的完全二叉树，对根节点、左子节点和右子节点中数值最小的与根节点进行交换位置，这样就成为小顶堆。对于节点更多的完全二叉树，我们也需要通过此方法，从下往上，从右往左地对每个非叶子结点进行调整成为小顶堆，每次调整了之后，若有交换位置的话，还需要对以“被交换位置的子节点”为根节点来进行调整，因为你使该节点的值变大了，他可能又大于其左右子节点了，所以需要一步一步往下调整。直到根节点调整完后，整棵完全二叉树就是小顶堆了。

小顶堆有了，就可以利用小顶堆的特性（根节点是堆中的最小值）进行排序了。每次将根节点取出来，然后将最后一个节点提到根节点（此时树少了一个节点，也就是少了最小值），再进行相应的调整使得该完全二叉树依旧是小顶堆，那么这时的根节点又是堆中的最小值，以此类推，每次取出最小值，就可以实现对一个数组的排序。

代码实现

void heapSort(int *a, int n) {
    //从下往上，从右往左将非叶子节点进行调整
    for(int i = n/2; i >= 1; i--)
        heapAdjust(a, i, n);
    //i就是目前堆的最后一个节点的下标
    for(int i = n; i > 1; i--) {
        //将最后一个提到根节点，并把根节点保存到a[i]处
        swap(a[1], a[i]);
        heapAdjust(a, 1, i - 1);
    }
}

void heapAdjust(int *a, int rt, int n) {
    for(int nex = rt * 2; nex <= n; nex *= 2) {
        //找两个子节点中更小的一个，用nex存其下标
        if(nex + 1 <= n && a[nex+1] < a[nex]) nex ++;
        if(a[rt] < a[nex]) break;
        //交换位置
        swap(a[rt], a[nex]);
        //以被交换位置的子节点根往下继续调整
        rt = nex;
    }
}