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

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;

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

What is the time complexity of finding the minimum element in a min heap?

c++

heap

min-heap