implementing ExtractMin on a Max-heap in O(log(n)) time
Suppose that there is an algorithm that examines a complete max-heap (i.e. one in which all leaves have the same depth) and outputs the minimum without accessing all leaves. Whenever the algorithm examines the value of an internal node, hand it the value 2, and whenever it examines the value of a leaf, hand it the value 1. The algorithm misses at least one leaf $\ell$, and so cannot tell the situation in which all leaves have the value 1 from the situation in which all leaves but $\ell$ have the value 1, and $\ell$ has the value 0.