堆排序

贡献者：有机物

预备知识　堆

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

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

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

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

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

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

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

　　 证明：

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

　　所以：

\begin{equation} \begin{aligned} &\quad\dfrac{n}{2} \times 1 + \dfrac{n}{4} \times 2 + \cdots + \dfrac{n}{2^{\left\lceil{\log_2 n}\right\rceil}} \times \left\lfloor{\log_2 n}\right\rfloor \\ &= \left\lfloor{\log_2 h}\right\rfloor \sum ^ {\left\lceil{\log_2 n}\right\rceil} _ {h=1} \dfrac{n}{2^h} \\ &= n(\dfrac{1}{2^2} + \dfrac{1}{2^3} + \dfrac{1}{2^4} + \cdots +\dfrac{1}{2^{\left\lceil{\log_2 n}\right\rceil}}) \\ &= n \sum^{\left\lceil{\log_2 n}\right\rceil} _ {h = 2} 2^h~.\\ \end{aligned} \end{equation}

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

\begin{equation} \begin{aligned} s &= \dfrac{1}{2^2} + \dfrac{1}{2^3} + \dfrac{1}{2^4} + \cdots +\dfrac{1}{2^{\left\lceil{\log_2 n}\right\rceil}}~,\\ 2s &= \dfrac{1}{2} + \dfrac{2}{2^2} + \dfrac{3}{2^3} + \cdots + \dfrac{\left\lceil{\log_2 n}\right\rceil}{2^{\left\lceil{\log_2 n}\right\rceil}}~,\\ 2s - s &= s= \dfrac{1}{2} + \dfrac{1}{2^2} + \dfrac{1}{2^3} + \cdots + \dfrac{1}{2^{\left\lceil{\log_2 n}\right\rceil}}~. \end{aligned} \end{equation}

因为 $s$ 是小于 $1$ 的，所以 $\sum^{\left\lceil{\log_2 n}\right\rceil} _ {h = 2} 2^h < 1$，所以时间复杂度为 $\mathcal{O}(n)$。因此堆排序的时间复杂度为 $\mathcal{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;
}