How to prove that a binary heap can't be sorted with complexity that better than O(nlogn) I am trying to prove that you can't sort binary heap with better complexity than O(nlogn).
We proved at class that every sort based on comparison can't have better cocmplexity than O(nlogn) and  i know nothing about the items in the heap (except its a heap) so you  can't use radix sort or linear sort.
Problem is i feel like its not enough to say this things.
I don't know how i am supposed to prove it and i am searching for help.
A binary heap with $n$ elements can be built in time $O(n)$. If there was a (comparison based) sorting algorithm capable $A$ of sorting the elements in a heap in time $o(n \log n)$ then you could obtain a (comparison-based) sorting algorithm $A'$ that works for arbitrary sequences $S$ of $n$ elements. Algorithm $A'$ is as follows:

Construct a heap $H$ from $S$.
Execute $A$ with input $H$.

Such an algorithm requires time $O(n) + o(n \log n) \in o(n \log n)$ and hence it contradicts the $\Omega(n \log n)$ lower bound on comparison-based sorting algorithm. Therefore, algorithm $A$ cannot exist.