std::priority_queue 如何完成 O(log n) 插入？
How does std::priority_queue accomplish O(log n) insertion?
documentation for std::priority_queue 表示 push 操作的复杂性为：
Logarithmic number of comparisons plus the complexity of Container::push_back.
并且默认使用 std::vector 作为底层容器。但是，push_back 只能将元素推到向量的末尾，而在优先级队列中，可能需要在向量的中间某处添加元素，在这种情况下，必须将后面的所有元素转移到正确的。在最坏的情况下，在开始添加元素时，推送操作将产生全部 O(n) 成本。那么优先队列是如何在对数时间内做到的呢？为什么它默认使用向量而不是一些“易于插入和查找”的容器，例如堆？
while in a priority queue one might need to add elements somewhere in the middle of the vector, in which case all elements that follow have to be shifted to the right
没有。没有发生右移。
新元素添加到末尾，在索引 i: O(1)
然后将其优先级与索引 i/2 处的父级进行比较，如果优先级更高则交换。
如果发生交换，比较下一个parent。
重复以上 2 个步骤，直到索引 0。 O(log(i))
documentation for std::priority_queue 表示 push 操作的复杂性为：
Logarithmic number of comparisons plus the complexity of
Container::push_back.
并且默认使用 std::vector 作为底层容器。但是，push_back 只能将元素推到向量的末尾，而在优先级队列中，可能需要在向量的中间某处添加元素，在这种情况下，必须将后面的所有元素转移到正确的。在最坏的情况下，在开始添加元素时，推送操作将产生全部 O(n) 成本。那么优先队列是如何在对数时间内做到的呢？为什么它默认使用向量而不是一些“易于插入和查找”的容器，例如堆？
while in a priority queue one might need to add elements somewhere in the middle of the vector, in which case all elements that follow have to be shifted to the right
没有。没有发生右移。
新元素添加到末尾，在索引 i: O(1)
然后将其优先级与索引 i/2 处的父级进行比较，如果优先级更高则交换。
如果发生交换，比较下一个parent。
重复以上 2 个步骤，直到索引 0。 O(log(i))