堆排序(Heapsort)

gaunthan Posted on Aug 7 2016

? Sorting ? ? Algorithm ?

## 思想
堆是一种特殊的数据结构，它可以在常数时间内获取结构中的最优值，随后以对数时间维护最优结构。我们可以执行 n 次这样的操作，这样就可以以 $O(nlogn)$ 时间进行排序。基于这种想法的排序算法叫做**堆排序**(heap sort)：先建立 n 个元素的二叉堆（花费 $O(n)$ 时间），然后执行 n 次 `DeleteMin` 操作（每次删除最小操作花费 $O(logn)$） ，因此总的运行时间是 $O(nlogn)$。

上面算法的主要问题在于使用了一个附加的数组，以存放输出结果，因此存储需求增加了一倍。然而这是可以避免的：在每次 DeleteMin 之后，堆缩小了1。因此，位于堆中最后的单元可以用来存放刚刚删去的元素。使用这种策略，在最后一次 DeleteMin 后，该数组将以递减的顺序包含这些元素。如果想要这些元素以递增的顺序排列，那么可以改变序的特性使堆成为一个最大堆。

总的来说，堆排序以 $O(nlogn)$ 时间复杂度，$O(1)$ 空间复杂度完成排序。注意堆排序是不稳定排序算法。

## 实现
假设输入是一个数组 a、与其元素个数 N，则使用堆排序对输入进行升序处理的实现如下：

1. 构建一个最大堆
2. 将堆中的最后元素与第一个元素交换，缩减堆的大小并进行下滤
3. 执行 n - 1 次第二步操作

代码如下：
```c
#define Parent(i) ((i) >> 1)
#define LeftChild(i) ((i) << 1)
#define RightChild(i) (((i) << 1) + 1)

/* 最大堆下滤操作 */
static void PercDown(ElementType a[], int i, int n)
{
    int child;
    ElementType tmp;
    for (tmp = a[i]; LeftChild(i) < n; i = child) {
        child = LeftChild(i);
        if (child != n - 1 && a[child + 1] > a[child]) 
            child++;
        if (tmp < a[child]) 
            a[i] = a[child];
        else 
            break;
    }
    a[i] = tmp;
}
 
/* 最大堆排序算法 */
void HeapSort(ElementType a[], int n)
{
    int i;
    for (i = n / 2; i >= 0; --i) // build heap
        PercDown(a, i, n);
    for (i = n - 1; i > 0; --i) { // deleteMax
        Swap(&a[0], &a[i]);              
        PercDown(a, 0, i); // 注意执行该下滤操作时，堆大小为i
    }
}
```

## References

- MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010.
- ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013.