二叉堆应用一：堆排序

什么是堆?

大根堆和小根堆.jpg

如图所示：当父结点的值，都比其子结点的值小时，就是小根堆，一个小根堆中，最小的值肯定在堆顶。

同理，当父结点的值都比其子结点的值大时，就是大根堆，一个大根堆中，最大的值肯定在堆顶。

堆排序

1.jpg

现在是一个大顶堆，那么最大值肯定在堆顶处，我们将堆顶的元素与最后一个元素交换。

步骤2.jpg

然后再将剩下的元素（排除交换的最后一个元素）重新调整为大根堆，过程如下：
10 与左儿子结点右儿子结点中最大值交换。

步骤3.jpg

此时有形成一个新的大根堆。我们在做第一步做

绘图4.jpg

此时，我们就将最大数，和第二大数排好序（升序排列）。
将这个过程往复下去，最后我们就能够将所有数据排序完毕。

我们上面所作的所有步骤，都是假设序列一开始就是大根堆的情况下，但是并不是所有将要排序序列一开始就是是符合大根堆的。

所以，其中关键就是构造大根堆。当我们第一次把随机的数组构造成大根堆后，以后我们只需要每次交换后调整堆顶的数据使之再成为大根堆。往复下去。

思路：

• precolate down（下溯算法）：

给定一个结点n， 其左子结点2n+1，右子节点：2n+2。然后与左右子结点中最大值childmax比较，如果大于childmax，则说明该结点及子树已经符合大根堆标准。
否则则与childmax交换，然后再把原childmax结点作为新的父结点和其左子结点和右子结点比较，作上述过程。最后一直下溯至叶子结点（叶子节点没有左右子结点）。这样我们将结点n及其子树调整为了大根堆。整个过程如上图3。

但是步骤3排序思路的大前提是我们已经将一个随机的数组已经有构造成大根堆的情况下。所以我们之前还必须做将一个随机数组构造成一个大根堆。

• 那怎么做将一个随机数组构造成一个大根堆？

有了步骤3 的思路，我们可以从最后一个非叶子结点开始，每一个按照步骤3调整，（这样，每一个结点调整后都可以保证该结点及其子树是副符合大根堆）。这样至下而上，直到根节点。完成后我们将一个随机数组调整为了大根堆。

代码实现

//  precolate down 将[n, lastIndex]的值调整为大根堆。
void HeapAdjust(vector<int> &vec, int n, int lastIndex)
{
    int leftChild = n * 2 + 1;    // 左儿子结点
    int rightChild = n * 2 + 2;  // 右儿子结点
    int lastNotLeave = (lastIndex-1)/2; // 最后一个非叶子结点。

    /* 如果当前结点不是叶子结点， 则调整 */
    if (n <= lastNotLeave) 
    {
         /* 左右子节点较大值结点的索引 */
        int maxIndex;    
        if (rightChild <= lastIndex)    // 该父结点有左右2个子结点
            maxIndex = vec[leftChild] >= vec[rightChild] ? leftChild : rightChild;
        else
            maxIndex = leftChild;
        /* 与当前结点值比较 */    
        if (vec[maxIndex] > vec[n]) 
        {
            swap(vec[maxIndex], vec[n]);
            /* 如果当左右子较大的结点不是是叶子结点， 则继续下溯调整 */
            if (maxIndex <= lastNotLeave)
                HeapAdjust(vec, maxIndex, lastIndex);
        }
    }
}

/* 第一次将一个随机数组调整为大根堆 */
void makeHeap(vector<int>& vec, int length)
{     
    /* 最后一个子树的父节点是(length-2)/2，从它开始上溯调整 */
    for (int i = (length-2)/2; i >= 0; i--)
        HeapAdjust(vec, i, length-1);
}

void HeapSort(vector<int>& vec, int length)
{     
    makeHeap(vec, length);
    for (int i = length - 1; i > 0; i--) 
    {
        swap(vec[i], vec[0]);
        HeapAdjust(vec, 0, i-1);    // 交换值之后，只需要调整第一个结点
    }
}

性能

平均时间	最差	最佳	辅助空间	稳定性
O(Nlog2N)	O(Nlog2N)	ONlog2N)	O(1)	不稳定