c++ - 插入 priority_queue : before the first occurence of that value instead of after the last occurence

Question

所以这是与此(Inserting in a multiset: before the first occurence of that value instead of after the last occurence)相同的问题，但针对的是 priority_queue。此外，任何有关何时使用什么的见解都会有所帮助。我看到 priority_queue.push 是 O(log(n))，但推送 n 个元素是 O(n)。这怎么可能？

Answer 1

一般来说，优先级队列不会根据到达时间对同等优先级的项目进行排序。如果你想这样做，你需要创建你自己的比较运算符，它不仅比较优先级值而且比较到达时间(或者可能是单调递增的序列号)。这里的关键是优先级队列本身并不关心插入顺序。

对于 C++，请参阅 https://en.cppreference.com/w/cpp/container/priority_queue有关优先级队列和 Compare 构造函数参数的更多信息。

参见 Priority Queue remove items with same priority first one entered解释为什么在作为二进制堆实现的优先级队列中，不可能确保相同优先级的项目按插入顺序(或相反顺序)被删除。

你说:

I see that priority_queue.push is O(log(n)) but pushing n elements is O(n). How is that possible?

不是。您不能将 n 个元素放入复杂度为 O(n) 的堆中。但是，您可以在 O(n) 时间内将 n 个元素的数组转换为堆。参见 How can building a heap be O(n) time complexity?了解详情。