我正在用C++编写一个应用程序，对于优先队列来说，具有O(1)的Dequeue操作至关重要，而Enqueue的复杂度则不那么重要（当然，除非它变成了n^2或2^n）。
最初我使用了链表。它非常适合Dequeue（O(1)），而且具有很好的Enqueue复杂度。唯一的问题是排序它。并不是使用O(n)复杂度的插入排序适合我的需求，而是排列链表本身非常麻烦。这太慢了。
向量根本不好。Dequeue将是O(n)，需要把所有元素向后移动一位。Enqueue仍然是O(n)，但速度要快得多。
你能提供更高效的方法吗？谢谢。
反向排序的 vector 具有O(1)的pop_back和O(n)的插入。
vector唯一的问题，那么你可以尝试使用deque。 - Steve Jessop您可以将队列存储为排序的链接列表。删除队列前端元素的时间复杂度为O(1)，在正确位置插入元素的时间复杂度为O(n)。
但是对链接列表进行排序很麻烦。速度很慢。
每次插入后不必执行完整的排序。您只需遍历（已排序）列表以查找新元素的正确位置，并在那里插入它。遍历的时间复杂度为O(n)，插入的时间复杂度为O(1)。
如果您愿意从文献中实现，那么我有一个更好的解决方案。
删除: O(1)
删除最小值: O(1)
查找最小值: O(1)
插入: O(log n)
如果允许MELD花费线性时间，则可以使用Dietz和Raman的指针搜索树
[3]来支持最坏情况下常数时间的DELETE-MIN。 通过使用他们的数据结构MAKEQUEUE，FINDMIN，DELETEMIN，DELETE可以在最坏情况下支持时间O(1)，INSERT在最坏情况下支持时间O(log n)，MELD在最坏情况下支持时间O(n)。
我们的数据结构使用随机访问机器(RAM)模型，具有单位成本度量和对数字大小;
最近，Pointer-Machine 计算模型中提出了一个解决方案[1]。它具有 O(1) 的 get-min、extract-min、get-max、extract-max 和 O(log n) 的 insert。
O(1) 弹出，而问题声称这是“关键”的。当然，有时人们会犯错误，并认为他们需要 O(1)，而实际上 O(log n) 是可以的。在实践中，log n < 64，因此 O(log n) 可以看作是较慢的 O(1)。 - Steve JessopO(1)弹出的优先队列，则通常的堆将被排除在外，当然，推送的性能也会相应受到影响。 - Steve Jessop可以将平衡二叉搜索树与链表相结合。树的每个元素都有指向其子节点的链接，还有指向前一个和后一个元素的链接。这样你就可以拥有：
O(lg n) 插入、删除、搜索；O(1) - 提取最小值和最大值
另一种可能性是使用跳表，如果您不介意使用随机结构，那么您也将拥有：
O(lg n) 插入、删除、搜索；O(1) - 提取最小值和最大值
O(n)）太慢了。下定决心吧 :-) - Steve JessopO(log n)。除非您详细说明了使删除操作比这更快速度如此重要的具体要求，否则您将无法获得最佳建议。可能是为了使删除器更加响应 I/O 或 GUI 等方面。与堆相比，您希望放弃整体性能以加快删除速度。但是您没有说整体上应该慢多少。 - Steve Jessop