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

Question

我正在阅读本文档中提到的Problem1(Part-b):

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

应该是这样,因为当我们构造一个最大堆时,时间复杂度O(logn)就像这里提到的那样.

同样,如果我构造一个min-heap,它应该是O(logn).min heap类似于max-heap,它只是在C++中,默认情况下构造了一个最大堆,我们将不得不为min-heap编写一个自定义比较器.然后,有什么区别？

Answer 1

在min-heap中找到最小元素的时间复杂度是O(1),这是这种容器的主要目的.它实际上是为了在恒定时间内找到最小(或最大)的元素.即操作O(logn)是插入.正如其他人所提到的那样,pop也是O(logn)因为它将删除最小(或最大)的元素,然后强制重新排序以确保新的最小(或最大)元素现在位于堆的顶部.

来自cppreference

优先级队列是一个容器适配器,它以对数插入和提取为代价,提供最大(默认情况下)元素的常量时间查找.

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

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