堆排序

贡献者： 有机物

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

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

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

1. 建堆；
2. 输出堆顶；
3. 删除堆顶。

　　 由于只有删除堆顶这个操作，所以只需要实现 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}$。

　　 所以：

　　 那么上面的公式是不是 $\mathcal{O}(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;
}