算法导论 - 堆排序算法

老王

与归并排序一样，但不同于插入排序的是，堆排序的时间复杂度是                              ；而与插入排序相同，但不同于归并排序的是，堆排序同样具有空间原址性，任何时候都只需要常数个额外的元素空间存储临时数据。因此，堆排序是集合了我们目前已经讨论的两种排序算法优点的一种排序算法。

堆排序引入了另一种算法设计技巧，使用一种称为“堆”的数据结构来进行信息管理。堆不仅用在堆排序中，而且也可以用于构造一种有效的优先队列。

(二叉)堆是一个数组，可以看作是一个近似的完全二叉树，树上的每一个结点对应数组中的一个元素，除了最底层外，该树是完全充满的，而且是从左向右填充。

二叉堆可以分为两种形式：最大堆和最小堆。在这两种堆中，结点的值都要满足堆的性质，但一些细节定义则有所差异。在最大堆中，最大堆性质是指除了根以外的所有结点i都要满足：A[i的父结点]≥A，也就是说，某个结点的值至多与其父结点一样大，因此，堆中的最大元素存放在根结点中，并且，在任一子树中，该子树所包含的所有结点的值都不大于该子树根结点的值。最小堆的组织方式正好相反：最小堆性质是指除了根以外的所有结点i都有：A[i的父结点]≤A，最小堆中的最小元素存放在根结点中。在堆排序算法中，我们使用的是最大堆，最小堆通常用于构造优先队列。

[C++] 纯文本查看 复制代码

#include <stdio.h>

// 维护最大堆的性质
void MaxHeapify(int arrInt[], size_t i, size_t nHeapSize)
{
    size_t nLeft  = 2 * i + 1;
    size_t nRight = 2 * i + 2;
    size_t nLarge;

    if (nLeft <= nHeapSize && arrInt[nLeft] > arrInt)
        nLarge = nLeft;
    else
        nLarge = i;

    if (nRight <= nHeapSize && arrInt[nRight] > arrInt[nLarge])
        nLarge = nRight;

    if (nLarge != i)
    {
        int nTemp = arrInt;
        arrInt = arrInt[nLarge];
        arrInt[nLarge] = nTemp;

        MaxHeapify(arrInt, nLarge, nHeapSize);
    }
}

// 数组转换为最大堆
void BuildMaxHeap(int arrInt[], size_t nLength)
{
    for (intptr_t i = nLength / 2; i >= 0; i--)
        MaxHeapify(arrInt, i, nLength);
}

// 堆排序（原址排序）
void HeapSort(int arrInt[], size_t nLength)
{
    BuildMaxHeap(arrInt, nLength);
    for (size_t i = nLength; i >= 1; i--)
    {
        int nTemp = arrInt[0];
        arrInt[0] = arrInt;
        arrInt = nTemp;

        nLength--;
        MaxHeapify(arrInt, 0, nLength);
    }
}

int main()
{
    int arrInt[] = { 88, -100, 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, -1, -2, -3, -4, -5 };
    size_t nCount = sizeof(arrInt) / sizeof(arrInt[0]);

    HeapSort(arrInt, nCount - 1);

    for (size_t i = 0; i < nCount; i++)
        printf("%d\n", arrInt);


    return 0;
}

堆排序是一个优秀的算法，但是在实际应用中，快速排序的性能一般会优于堆排序，尽管如此，堆这一数据结构仍然有很多应用。