c++ - 为什么插入和提取 std::priority_queue 都需要对数时间？

Question

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和 std::priority_queue::pop在他们的复杂性描述中提到:

Complexity

Logarithmic number of comparisons

为什么两者都必须进行比较？对于保持分类的内部容器，提取应该很容易，反之亦然，提取时进行分类，插入应该很容易。

我想我关于排序发生的时间和方式(或者是否发生任何排序)的假设是错误的。有人可以解释一下吗？

Answer 1

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) 插入和提取。该结构是一棵树，插入/提取只是保持树不变。对于某些问题(例如，搜索)，在我们需要插入和提取许多节点的情况下，两个操作的 O(lg n) 远优于 O(n)/O(1)。

举个例子，从维基百科窃取图像，将元素 15 插入堆中最初会将其放置在位置 x:

然后将它与 8 交换(因为已排序的不变量被破坏):

然后最后将它与 11 交换:

在数组形式中，初始堆将存储为:

[11, 5, 8, 3, 4]

我们最终会在:

[15, 5, 11, 3, 4, 8]

提取只是相反的操作——向下冒泡而不是向上冒泡。如您所见，没有进行明确的“排序”。大多数时候我们甚至没有接触到大部分元素。

---

^†std::priority_queue是一个容器适配器，但是你提供的容器应该是一个O(1)的随机访问容器索引、push_back、pop_back、front、back 等的复杂性。所以容器的选择(除非你make a bad one) 不会影响 priority_queue 操作的整体复杂性。