缩小std::priority_queue

Question

给定添加元素的速度比通过重复弹出最佳元素的通常过程移除元素的速度更快的std::priority_queue，使得程序将耗尽存储器，除非执行了某些操作，

有没有办法丢弃最差的一半元素，而让最好的一半像往常一样一次处理一个呢？

Answer 1

没有直接的方法。但是二进制堆无论如何都不能真正支持这个操作。

但要间接做到这一点并不难：

• Create a temporary empty priority queue
• 交换主队列和临时队列
• 进入一个循环，该循环从临时队列弹出并推送到主
• Stop，当您对复制的临时队列数量感到满意时。

Answer 2

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

Answer 3

std::priority_queue是一个2-heap，因此只有部分排序。与提取元素不同，数据结构对于定位元素的最佳一半没有用处。