c++ - 具有 O(1) 出队和 O(whatever) 入队的优先级队列

Question

我正在用 C++ 编写一个应用程序，其中对优先级队列进行 O(1) 出队操作至关重要，而入队的复杂性并不那么重要(除非它变成 n^2 或 2^n当然)。

一开始我用的是链表。它非常适合出队 (O(1))，并且具有良好的入队复杂度。唯一的问题是，对其进行排序。并不是说使用具有 O(n) 复杂度的插入排序就可以满足我的需要。但是对链表进行排序是一件痛苦的事情。太慢了。

vector 一点也不好。出队将是 O(n) 以将所有元素移回一个位置。入队仍然是 O(n)，但速度要快得多。

你能推荐更高效的方法吗？谢谢。

Answer 1

反向排序的vector 有 O(1) pop_back 和 O(n) 插入。