I've been given the following problem:Given a data structure $M$ that is based on comparisons and supports the following methods on a group of numbers $S$:$\text{Insert}(x)$  add $x$ to $S$$\text{Extract_min}()$  remove the minimal element in $S$ and return it We can implement with a heap the above methods in $O(\log n)$, however, we're looking at a bigger picture, a general case that we have no guarantee that $M$ is indeed a heap. Prove that no matter what kind of data structure $M$ is, that at least one of the methods that $M$ supports must take $\Omega(\log n )$.My solution:Each sorting algorithm that is based on comparisons must take at the worst case at least $\Omega(n\log n)$  we'll prove that using a decision tree: if we look at any given algorithm that is based on comparisons, as a binary tree where each vertex is a compare-method between 2 elements: if the first is bigger than the second element  we'll go to the left childif the second is bigger than the first element  we'll go to the right childAt the end, we'll have $n!$ leaves that are the options for sorting the elements.The height of the tree is $h$, then:$$2^h \ge n! \quad\Longrightarrow\quad \log(2^h) >= \log(n!) \quad\Longrightarrow\quad h \ge \log(n!) \quad\Longrightarrow\quad h = \Omega(n \log n)$$Then, if we have a $\Omega(n \log n)$ worst case for $n$ elements, then we have a $\Omega(\log n)$ for a single element. I'm not sure regarding this solution, so I'd appreciate for corrections or anything else you can come up with. 
Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?
algorithms;data structures;binary trees;search trees