为什么插入和提取into/from a std::priority_queue都需要对数时间？
Why do both insertion and extraction into/from a std::priority_queue take logarithmic time?
A [std::priority_queue] is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
这是为什么？我认为排序要么发生在插入时，要么发生在提取时。
例如，如果排序发生在插入时并且内部容器保持排序，那么提取是否能够在恒定时间内发生？要删除的顶部元素是已知的，下一个较小的元素也是已知的。
然而，两者 std::priority_queue::push and std::priority_queue::pop 在他们的复杂性描述中都提到：
Complexity
Logarithmic number of comparisons
为什么 both 必须进行比较？对于保持分类的内部容器，提取应该很容易，反之亦然，提取时进行分类，插入应该很容易。
我想我关于排序发生的时间和方式（或者是否发生任何排序）的假设是错误的。有人可以解释一下吗？
出栈操作，移除最上面的元素。有几种实现优先级队列的方法，但在所有这些方法中，删除顶部是对数的。来自 wiki - Priority queue。
For example, if the sorting happens on insertion and the internal container remains sorted, wouldn't the extraction be able to happen in constant time?
提取可能会在常数时间内发生，但插入会变为 O(n)。您必须在列表中搜索位置以插入新元素，然后移动所有其他元素。 O(1) 提取和 O(n) 插入可能适用于某些用例，但不是 priority_queue 试图解决的问题。
另一方面，如果排序发生在提取时，那么您将进行 O(n lg n) 提取和 O(1) 插入。这同样适用于某些用例，但这不是 priority_queue 所做的。
std::priority_queue 不是对元素进行排序，而是将其元素 † 存储在 heap 中，根据构造，它具有 O(lg n) 插入和提取。结构是一棵树，insertion/extraction只是简单地保持了树的不变性。对于某些问题（例如，搜索），在我们需要插入和提取许多节点的情况下，两个操作都使用 O(lg n) 远远优于 O(n)/O(1)。
举个例子，从维基百科窃取图像，将元素 15 插入堆中最初会将其放置在位置 x:
然后将其与 8 交换（因为已排序的不变量被破坏）：
然后最终将其与 11 交换：
在数组形式中，初始堆将存储为：
[11, 5, 8, 3, 4]
我们最终会在：
[15, 5, 11, 3, 4, 8]
提取只是相反的操作——向下冒泡而不是向上冒泡。如您所见，没有明确的 "sorting" 进行。大多数时候我们甚至没有接触到大部分元素。
†std::priority_queue是一个容器适配器，但是你提供的容器应该是一个随机访问容器，索引复杂度O(1)，push_back、pop_back、front、back等。所以容器的选择（除非你做的不好）不影响priority_queue的整体复杂度操作。
A [
std::priority_queue] is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
这是为什么？我认为排序要么发生在插入时，要么发生在提取时。 例如，如果排序发生在插入时并且内部容器保持排序，那么提取是否能够在恒定时间内发生？要删除的顶部元素是已知的，下一个较小的元素也是已知的。
然而，两者 std::priority_queue::push and std::priority_queue::pop 在他们的复杂性描述中都提到：
Complexity
Logarithmic number of comparisons
为什么 both 必须进行比较？对于保持分类的内部容器，提取应该很容易，反之亦然，提取时进行分类，插入应该很容易。
我想我关于排序发生的时间和方式（或者是否发生任何排序）的假设是错误的。有人可以解释一下吗？
出栈操作，移除最上面的元素。有几种实现优先级队列的方法，但在所有这些方法中，删除顶部是对数的。来自 wiki - Priority queue。
For example, if the sorting happens on insertion and the internal container remains sorted, wouldn't the extraction be able to happen in constant time?
提取可能会在常数时间内发生，但插入会变为 O(n)。您必须在列表中搜索位置以插入新元素，然后移动所有其他元素。 O(1) 提取和 O(n) 插入可能适用于某些用例，但不是 priority_queue 试图解决的问题。
另一方面，如果排序发生在提取时，那么您将进行 O(n lg n) 提取和 O(1) 插入。这同样适用于某些用例，但这不是 priority_queue 所做的。
std::priority_queue 不是对元素进行排序，而是将其元素 † 存储在 heap 中，根据构造，它具有 O(lg n) 插入和提取。结构是一棵树，insertion/extraction只是简单地保持了树的不变性。对于某些问题（例如，搜索），在我们需要插入和提取许多节点的情况下，两个操作都使用 O(lg n) 远远优于 O(n)/O(1)。
举个例子，从维基百科窃取图像，将元素 15 插入堆中最初会将其放置在位置 x:
然后将其与 8 交换（因为已排序的不变量被破坏）：
然后最终将其与 11 交换：
在数组形式中，初始堆将存储为：
[11, 5, 8, 3, 4]
我们最终会在：
[15, 5, 11, 3, 4, 8]
提取只是相反的操作——向下冒泡而不是向上冒泡。如您所见，没有明确的 "sorting" 进行。大多数时候我们甚至没有接触到大部分元素。
†std::priority_queue是一个容器适配器，但是你提供的容器应该是一个随机访问容器，索引复杂度O(1)，push_back、pop_back、front、back等。所以容器的选择（除非你做的不好）不影响priority_queue的整体复杂度操作。