c++ - 在最小堆中找到最小元素的时间复杂度是多少？

Question

我正在阅读 this document 中提到的问题 1(B 部分) :

Finding the minimum element of a binary min heap takes logarithmic time: T/F?

这应该是真的，因为当我们构造一个最大堆时，时间复杂度是O(logn)如前所述here .

同样，如果我构造一个最小堆，它应该是O(logn)。最小堆类似于最大堆，只是在 C++ 中，默认构造最大堆，我们必须为最小堆编写自定义比较器。那么，有什么区别呢？

Answer 1

在最小堆中找到最小元素的时间复杂度为 O(1)，这是此类容器的主要目的。从字面上看，它是为了在恒定时间内找到最小(或最大)的元素。 O(logn) 的操作是插入。正如其他人提到的，pop 也是 O(logn) 因为它将删除最小(或最大)的元素，然后强制重新排序以确保新的最小(或最大)元素现在位于堆的顶部。

来自 cppreference

A 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。 ，如果你想要一个最大堆，你使用 std::less，如果你想要一个最小堆，你使用 std::greater 作为 Compare模板参数

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;