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

Question

我正在阅读本文档中提到的问题 1（b 部分）：

找到二进制最小堆的最小元素需要对数时间： T / F？

应该是真的，因为当我们构造一个最大堆时，时间复杂度就是这里O(logn)提到的。

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

Answer 1

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

来自cppreference

优先级队列是一个容器适配器，它以对数插入和提取为代价，提供对最大（默认情况下）元素的恒定时间查找。

出于所有意图和目的，除了比较器之外，最小堆和最大堆是完全相同的。事实上，在实践中，最小堆通常是 a std::priority_queue，如果你想要一个 maxheap std::less，如果你想要一个 minheap ，你使用 astd::greater作为Compare模板参数

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