c++ - 缩小 std::priority_queue

Question

给定一个 std::priority_queue 元素被添加到其中的速度比通过重复弹出最佳元素的通常过程删除它们的速度要快，因此除非执行某些操作，否则程序将耗尽内存，

有什么方法可以丢弃最差的一半元素，同时让最好的一半像往常一样一次处理一个？

Answer 1

显然不是，因为 std::priority_queue 的接口非常有限。您可以实现自己的优先级队列，让您可以使用 make_heap、push_heap 和 pop_heap（这就是 std::priority_queue 的实现方式）并实现自己的函数来删除最差的一半元素。

Answer 2

没有直接的方法。但无论如何，二进制堆并不真正支持该操作。

但间接地这样做并不难：

• 创建一个临时的空优先级队列
• 交换主队列和临时队列
• 输入一个从临时弹出并推送到主的循环
• 当您对复制元素的数量感到满意时停止
• 销毁临时队列。

Answer 3

这std::priority_queue是一个 2 堆，因此仅部分排序。数据结构对于定位元素的最佳一半而不是提取它们没有用处。