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

Question

I was reading Problem1 (Part-b) mentioned in this document:

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

It should be true, because when we construct a max-heap, the time complexity is O(logn)as mentioned here.

Similarly, if I construct a min-heap, it should be O(logn). A min heap is analogous to max-heap, its just that in C++, by default a max heap is constructed, and we will have to write a custom comparator for min-heap. Then, what's the difference?

Answer 1

The time complexity to find the minimum element in a min-heap is O(1), that is the primary purpose of such a container. It was literally made to find the smallest (or largest) element in constant time. The operation that is O(logn) is insertion. As others have mentioned, pop is also O(logn) because it will remove the smallest (or largest) element, and then force a re-ordering to ensure that the new smallest (or largest) element is now at the top of the heap.

From 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.

For all intents and purposes, a min heap and a max heap are the exact same thing except for the comparator. In fact, in practice a min heap is generally a std::priority_queue, and if you want a maxheap you use std::less and if you want a minheap you use a std::greater for the Compare template argument

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