pb_ds 的若干使用方法

pb_ds 提供的数据结构都需要使用命名空间 __gnu_pbds，以下介绍几种常用的数据结构。

可并堆：__gnu_pbds::priority_queue

头文件 <ext/pb_ds/priority_queue.hpp>，声明方式与 std::priority_queue 类似，大部分用法也与一致。

关键的合并操作是 x.join(y)，其中 x 和 y 为两个 __gnu_pbds::priority_queue，表示将 y 合并到 x 上。值得注意的是，在进行此操作后 y 就为空了。

对于时间复杂度，特殊的一点是每种操作的复杂度取决于使用可并堆的类型。

如果只声明数据类型（或者及其比较类型），则默认使用的是配对堆（pairing_heap_tag），复杂度对于 pop 和 join 是 \(\mathcal O(1)\) 的，而对于 pop 是最坏 \(\mathcal O(n)\) 均摊 \(\mathcal O(\log n)\) 的。

要选择可并堆的类型，需要在数据类型（或比较类型）后声明对应类型。但是几乎没用，不如配对堆。