堆排序

贡献者：有机物

预备知识　堆

　　前文讲到了 “堆” 这个数据结构，这里来讲一下堆排序这个排序算法。

　　堆排序是用二叉堆这种数据结构实现的排序算法，从小到大排序的话是实现小根堆，而从大到小则相反。这里以实现从小到大排序为例。

　　具体做法是每次假设堆已经建好了，由于是小根堆，所以只需每次输出堆顶元素，再把堆顶删除，涉及到了三种操作：

建堆；
输出堆顶；
删除堆顶。

　　由于只有删除堆顶这个操作，所以只需要实现 down 操作。那如何来建堆呢？朴素方法是一个一个往堆中插入，但这种方法太慢了，有一个 $O (n)$ 的建堆方式，就是从 $\frac{n}{2}$ down 到 $1$ 就可以了。

　　为什么从 $\frac{n}{2}$ 开始 down 呢？假设堆中共有 $n$ 个结点， $n$ 结点的下标最大， $\frac{n}{2}$ 这个结点是有子结点的最大值，显然叶结点一定满足堆的性质，所以只需从 $\frac{n}{2}$ 开始建堆就能把堆建好。

　　为什么建堆的时间复杂度是 $O (n)$ 呢？这里简单的地来证明一下。

　　 证明：

　　一棵完全二叉树上有 $⌈ \log_{2} n ⌉$ 层，叶子结点没有结点了，所以叶子结点不需要 down，所以从 $\frac{n}{2}$ 开始 down，所以除了叶子结点，上面的所有结点的个数为 $\frac{n}{2}$ ，除去叶子结点，上面的最后一层结点就是 $\frac{n}{4}$ 。

　　所以：

\begin{matrix} (1) & \begin{aligned} \frac{n}{2} \times 1 + \frac{n}{4} \times 2 + \dots + \frac{n}{2^{⌈ \log_{2} n ⌉}} \times ⌊ \log_{2} n ⌋ \\ = ⌊ \log_{2} h ⌋ \sum_{h = 1}^{⌈ \log_{2} n ⌉} \frac{n}{2^{h}} \\ = n (\frac{1}{2^{2}} + \frac{1}{2^{3}} + \frac{1}{2^{4}} + \dots + \frac{1}{2^{⌈ \log_{2} n ⌉}}) \\ = n \sum_{h = 2}^{⌈ \log_{2} n ⌉} 2^{h} . \end{aligned} \end{matrix}

　　那么上面的公式是不是 $O (n)$ 的呢？

\begin{matrix} (2) & \begin{aligned} s & = \frac{1}{2^{2}} + \frac{1}{2^{3}} + \frac{1}{2^{4}} + \dots + \frac{1}{2^{⌈ \log_{2} n ⌉}}, \\ 2 s & = \frac{1}{2} + \frac{2}{2^{2}} + \frac{3}{2^{3}} + \dots + \frac{⌈ \log_{2} n ⌉}{2^{⌈ \log_{2} n ⌉}}, \\ 2 s - s & = s = \frac{1}{2} + \frac{1}{2^{2}} + \frac{1}{2^{3}} + \dots + \frac{1}{2^{⌈ \log_{2} n ⌉}} . \end{aligned} \end{matrix}

因为

s

是小于

1

的，所以

\sum_{h = 2}^{⌈ \log_{2} n ⌉} 2^{h} < 1

，所以时间复杂度为

O (n)

。因此堆排序的时间复杂度为

O (n \log_{2} n)

。

　　证毕。

　　 down 操作在堆这篇文章讲了，这里不再赘述。

　　由于堆排序并没有设计到随机删除或修改，所以直接交换堆中的元素即可，不需要使用复杂度特殊的堆交换方式。

　　数组模拟堆排序：

const int N = 1e5 + 10;
int n, cnt;
int h[N];

void down(int u)
{
    int t = u;
    if ((u << 1) <= cnt && h[u << 1] < h[t]) t = u << 1;
    if ((u << 1 | 1) <= cnt && h[u << 1 | 1] < h[t]) t = u << 1 | 1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    cnt = n;
    
    for (int i = n / 2; i; i -- ) down(i);
    
    while (n -- )
    {
        cout << h[1] << ' ';
        h[1] = h[cnt -- ];
        down(1);
    }
    
    return 0;
}

　　由于堆排序并没有涉及到随机删除或修改，因此可以用 C++ STL 库里的优先队列。

int main()
{
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> heap;  // 定义小根堆方式
    
    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        heap.push(x);
    }
    
    for (int i = 0; i < n; i ++ )
    {
        cout << heap.top() << ' ';  // 堆顶就是最小值
        heap.pop();  // 删除堆顶
    }
    
    return 0;
}

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。