Is it possible to implement extractMin on a Max-Heap in O(log(n)) time, and if so how? Or do you need a more elaborate structure like a max-min heap?
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.