C++ 中 priority_queue 的时间复杂度

Question

我一直在努力计算 priority_queue 的时间复杂度。 This post这里说这个容器的复杂度取决于底层容器。我的问题是 priority_queue 声明为

    using mypair = std::pair<int, int>;
    std::priority_queue<std::pair<int, mypair>, std::vector<std::pair<int, mypair>>, std::greater<std::pair<int, mypair>>> heap;

push 和 pop 的时间复杂度是多少 O(log(n))

Answer 1

堆插入和提取相对于树的高度具有最坏情况的复杂性，因此 O(log N)，加上底层数据结构的复杂性。

在 vector 的情况下，push_back 的摊销复杂度为 O(1)，而 pop_back O(1)。

因此可以说 push 和 pop 的总时间复杂度由 vector 支持的 priority_queue 为 O(log N)。

C++ 中 priority_queue 的时间复杂度

time complexity of priority_queue in C++

c++

time-complexity