I’ve some intuition that why this is true.
Since a min heap just tells the minimum element and the relationship between only parent and its children is known. There is no information about the relative ordering of elements in different sub trees of a same root. Thus it has to take more than O(n). But I want to know how to answer such questions with solid logic.
You are right.I think the reason might be given as -
So, sorting has a worst case complexity of omega(n*logn)(don’t consider bounded ranges for input and assume you have no idea about the pattern or the structure of the elements to be sorted from beforehand).Now, building a heap a heap takes O(n) time . Now , if you can exploit the min heap to property to print all the elements in O(n) time,then essentially you have spit out(sorted) the keys in a sorted order, thus bringing down the complexity to
omega(n) which leads to a contradiction.