std::priority_queue是如何实现O(log n)时间复杂度插入操作的？

为什么push操作可以做到对数时间复杂度？ #

首先要明确：std::priority_queue的底层实现是二叉堆，而标准库的二叉堆是基于完全二叉树的数组实现，完全不需要在数组中间插入元素。
插入操作的完整流程是：

• 先调用底层容器的push_back把新元素追加到数组末尾，这一步对于std::vector来说是*摊销O(1)*的开销
• 然后执行**上浮（sift up）**操作：从末尾元素开始，不断和父节点比较，如果优先级更高就交换两个元素，直到满足堆的性质为止。完全二叉树的高度是log₂n，因此最多只需要O(logn)次比较和交换，不需要移动数组中其他无关元素。
  这也和官方文档的复杂度说明完全吻合：

对数级别的比较次数加上Container::push_back的复杂度。
总复杂度稳定为O(logn)，不存在最坏O(n)的情况。

为什么默认选择std::vector作为底层容器，而非“堆”容器？ #

首先纠正一个常见误区：C++标准库中没有独立的「堆」容器，我们常说的std::make_heap、std::push_heap、std::pop_heap都是作用于随机访问容器的算法，不是容器类型。
选择std::vector作为默认底层容器的原因非常直接：

• 二叉堆算法依赖O(1)随机访问才能保证高效，std::vector刚好满足这个要求
• std::vector的push_back/pop_back都是摊销O(1)的开销，性能极高
• std::vector使用连续内存存储，缓存友好性远高于其他可选容器（比如std::deque的内存是分块的），在绝大多数场景下性能表现更优
  当然std::priority_queue也支持自定义底层容器，只要容器满足随机访问、支持push_back、pop_back、back操作即可，你也可以根据场景选择std::deque等其他容器，但默认的std::vector已经是综合性能最优的选择。

内容的提问来源于stack exchange，提问作者Wais Kamal