使用优先级队列结构？
在 C++ 标准库文档中搜索某些函数时，我读到优先级队列的推送和弹出需要恒定的时间。
http://www.cplusplus.com/reference/stl/priority_queue/push/< /a>
常量（在priority_queue中）。尽管请注意，push_heap 以对数时间运行。
我的问题是使用什么样的数据结构来维护优先级队列，其推送和弹出操作的复杂度为 O(1)？
While searching for some functions in C++ standard library documentation I read that push and pop for priority queues needs constant time.
http://www.cplusplus.com/reference/stl/priority_queue/push/
Constant (in the priority_queue). Although notice that push_heap operates in logarithmic time.
My question is what kind of data structure is used to maintain a priority queue with O(1) for push and pop ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
我假设您指的是 cplusplus.com 页面。
该页面早些时候写着：
因此，在
O(1)推送之后，数据结构已经失去了其堆属性不变性，并且将始终遵循O(log N)调用 恢复该属性。换句话说，O(1)操作只是整个操作的一部分；完整的操作是O(1) + O(log N)，与O(log N)相同。我猜他们提到这一点的原因是优先级队列是一个适配器，他们试图强调底层容器的功能与适配器的功能之间的区别。
I assume you are referring to cplusplus.com's page.
Earlier on the page it says:
So, after the
O(1)push, the data structure has lost its heap property invariant and will then always follow that with anO(log N)call to restore that property. In other words, theO(1)operation is only one part of the entire operation; the full operation isO(1) + O(log N)which is the same asO(log N).I guess the reason they mention that is that priority queue is an adapter and they are trying to emphasize the difference between what the underlying container does vs what the adapter does.
Priority_queue 的底层存储可以是向量、双端队列或任何支持随机访问迭代器的类似存储。存储以堆的形式维护，对于推送来说这不是 O(N)，所以我怀疑你读错了
The underlying storage for priority_queue can be a vector or a deque or anything similar that supports random access iterators. The storage is maintained as a heap, which is not O(N) for push, so I suspect you have read this wrong
根据
http://www.cppreference.com/wiki，Push 和 Pop 以对数时间运行/stl/priority_queue/pop
http://www.cppreference.com/维基/stl/priority_queue/push
Push and Pop run in Logarithmic time according to
http://www.cppreference.com/wiki/stl/priority_queue/pop
http://www.cppreference.com/wiki/stl/priority_queue/push
我对 O(1) 声明持怀疑态度......你在哪里看到它？
无论如何，这里有一些关于 gcc 优先级实现的注释队列。
I'm skeptical about the O(1) claim... where did you see it?
In any case, here are some notes on gcc's implementation of a priority queue.
不存在这样的堆。他们写道，它调用push_heap，它是对数的，所以它是logn。
There is not such a kind of heap. They have written that it calls push_heap which is logarithmic so it is logn.
该标准根据
push_heap和pop_heap定义了这些成员，这意味着编译性。如果该引用所说的是真的（它说
top< /code> 也是常量），为什么没有人使用 std::priority_queue 实现通用 O(N) 排序？其次，这就是参考文献可能试图以一种非常误导性的方式表达的内容：复杂性是
push_backO(1) +push_heap(O(日志N))The standard defines those members in terms of
push_heapandpop_heap, which implies the compilexity.If what that reference says is true (it says
topis also constant), why doesn't anybody implement general-purpose O(N) sorting usingstd::priority_queue?On second though, this is what the reference may be trying to say, in a very misleading way: the complexity is that of
push_backO(1) +push_heap(O(log N))