优 先 队 列 超 进 化

· · 个人记录

upd：复杂度证明。

注意看，这里有一只可可爱爱的优先队列，它支持以 O(f(n)) 的复杂度实现 push，pop 和 top。或许 f(n) 非常小，但无奈实现出来的优先队列功能上实在是有点呆。现在我们可以对它进行一些加装。

1.

我们考虑支持删除。维护另一个优先队列存被删掉的，每次看堆顶俩一样的就一起 pop。删数太多就重构。

现在我们支持了 O(f(n)) 的 erase。以下我们不再考虑 pop 这个操作。

2.

我们考虑优化 push 和 top 的复杂度。我们对数据建立一个类似于缓存块的东西，每次 push 就给扔进缓存里，缓存满 f(n) 了就把最值丢进优先队列里然后开新的缓存。erase 先在缓存内处理再考虑对优先队列的影响。这样 push 就是在 O(f(n)) 的复杂度内加入了 O(f(n)) 个数，摊下来变成了 O(1)。至于 top，我们每次 push 直接对着更新一下，erase 的时候重查就可以了，和 erase 的复杂度被摊到了一起，本体也变成了 O(1)。

（这个是 Dijkstra 做的工作。）

3.

现在这个堆的表现已经不错了，但它依然只能一个一个数加入。我们考虑把它进行一个可并化改造。维护一个并查集（按秩和路压都要），每个节点上存一个堆存当前点的数和所有儿子堆里的极值。这样 merge 就直接并查集连边就行（如 erase 对 pop 一样，以下我们不再考虑 push），top 就在并查集的根上找就行（注意只会在 erase 里更新所以一样摊过去是 O(1)）。至于 erase，处理一下到根的链就行，复杂度分析可以参照并查集。但事实上我们可以给出进一步分析，懒得抄 paper 的四类分讨了，总之可以证明 merge 和 top 摊出来都是常数时间，而 erase 摊出来是 O(f(n)\alpha(n,\frac{n}{f(n)}))。

上面这个式子看起来有不小的额外代价，但实际上让我们回顾 \alpha(m,n) 的定义，是为 \min\{z|A(z,4\lceil\frac mn\rceil)\gt\log_2n\}。而在此第二个参数是 O(f(n)) 的，这实际上启示我们，只要 f 不要太抽象比如 O(1)（这时候会多 \alpha），绝大部分情况下这个改造是没有额外代价的。举个例子，如果 f(n)=\Omega(\log^*n)，那这个 \alpha 就是真常数。

注意这一步需要 f(n) 不要太大，但反正有意义的讨论一定能给出 f(n)=O(\log n) 所以无需在意。

（这个是 Tarjan 做的工作。）

综上所述，现在我们把 O(f(n)) push，pop 和 top 的优先队列加装成了 O(1) merge 和 top，O(f(n)) pop 的超级优先队列。比较残念的是不支持 decrease_key，有点难过。

以上。

回复一下评论区：路压是因为你要 erase。作为单个堆而言做到那个复杂度是平凡的，但对于可能出现的亚 \log 堆，这个东西本质上是一台轮椅，实现好几个基础功能就能接近完全体，而不是真的用来拐 std::priority_queue。