priority_queue貌似是堆实现的
by zfx_VeXl6 @ 2022-08-15 22:24:08
@[zfx1569](/user/555301) 所以答案是什么捏
by MY（一名蒟蒻） @ 2022-08-15 22:25:32
@[MY（一名蒟蒻）](/user/240191)
1.没有。
2.无法实现。
by Qing_fy @ 2022-08-15 22:35:15
1. 懒惰删除，给这个元素打个标记，出堆的时候判断是不是删了，参见 Dijkstra 堆优化。直接做是不行的，但可以考虑 `std::multiset`。
2. 如果可以 $O(n)$ 遍历优先队列，就能 $O(n)$ 排序了？
by yukimianyan @ 2022-08-15 22:35:34
@[yukimianyan](/user/509229) 2不能暴力遍历吗
by xs_siqi @ 2022-08-15 22:37:14
@[MY（一名蒟蒻）](/user/240191)
你可以考虑使用 multiset，这个里面删除 $O(log n)$，遍历 $O (n log n)$
by Qing_fy @ 2022-08-15 22:37:55
@[xs_siqi](/user/401088) 理论上是可以的，但是访问堆顶+删除堆顶是 $O(log n)$ 的。
by Qing_fy @ 2022-08-15 22:38:55
@[Qing_fy](/user/461366) `std::multiset` 遍历 $O(n)$。
by xyf007 @ 2022-08-15 22:42:22
@[xyf007](/user/68273) 谢谢你喷我这个不懂装懂的屑。
by Qing_fy @ 2022-08-15 22:48:09
@[Qing_fy](/user/461366) 不懂装懂被他人嘲讽，至今过去5分钟，警钟长鸣。
by Qing_fy @ 2022-08-15 22:48:43