堆排序

STL 中的堆

如果要使用 $stl$ 中的堆（优先队列）：

#include <queue>
typedef pair<int, int> PII;

int main()
{
    priority_queue<int, vector<int>, greater<int>> myheap1;
    priority_queue<PII, vector<PII>, greater<PII>> myheap2;
}

其中：默认是大根堆，使用 greater<int> 创建的是小根堆。使用 pair 类型时，一般 first 放需有比较意义的数值，second 一般放标记号（比如堆优化版的 $Dijkstra$）。

目前比较有印象的，可以用到堆的题目有：前 K 小个数、堆优化Dijkstra，动态中位数（对顶堆）…

手写堆

堆是一个完全二叉树。小根堆约定父节点小于其左右子节点（如果有的话）。

$down$ 操作：
需要明确一点：在 heap[N] 数组中存储完全二叉树，约定根节点编号为 $idx = 1$；对于编号为 $idx$ 的点，其左儿子编号为 $2 \times idx$，右儿子编号为 $2 \times idx + 1$ 。

//down操作(小根堆)
void down(int idx)
{
    int t = idx;
    //在三个节点中找最小值
    if(idx * 2 <= n && heap[t] > heap[idx * 2]) t = idx * 2;
    if(idx * 2 + 1 <= n && heap[t] > heap[idx * 2 + 1]) t = idx * 2 + 1;
    if(idx != t)//根节点不是最小值才有必要交换
    {
        swap(heap[idx], heap[t]);
        down(t);//当前交换完不一定就是最终结果，需要递归处理
    }
}

另外，一般堆的建立操作时间复杂度是 $O(nlogn)$，但是有技巧让建堆操作的时间复杂度为 $O(n)$ 。

//时间复杂度为O(n)的建堆方法
for(int i = 1; i <= n; ++i)
    scanf("%d", &heap[i]);
for(int i = n / 2; i >= 1; --i)
    mydown(i);

堆顶元素删除操纵。采用先将堆中最后一个元素覆盖掉堆顶元素，再删除堆中最后一个元素的方法。

heap[1] = heap[size--], down(1);

手写堆的难度到这里都还算正常，后面的几项操作实在是XX，有种 $A$ 映射到 $B$，$B$ 再映射到 $C$ 的感觉。