c++ - 优先队列的push和pop和max_heap的插入和删除的时间复杂度是一样的吗？

Question

我对优先级队列的推送弹出和 max_heap 的插入删除的时间复杂度感到困惑。当输入很长(如 10^5)时它们是否需要相同的时间？？哪个会是更快的优先级队列或 max_heap？我正在尝试解决输入很长的问题。但是当我使用堆时，我得到运行时错误。

Answer 1

priority_queue 是以堆的形式实现的，它只是提供了保证堆不变量保持不变的接口(interface)(不像使用普通的 vector + make_heap ，它最初是一个堆，但开发人员可以通过随后直接滥用 vector 来破坏不变量) .
如果您对 make_heap 的结果有问题，而 priority_queue 没有，这可能是因为您操作堆的代码不正确；它们都应该同样有效( priority_queue 只是为您简化了一些事情)。没有复制器，我不能说你做错了什么。