$.$ Is it possible to design a min$-$help that supports both INSERT and EXTRACT$-$MIN in

time o$($log n$)?$ The answer is NO$,$ we can use that heap and sort $$n$$ numbers in o$($n log n$)$

time in comparison model $($i$.$e$.,$ insert all numbers first, then do EXTRACT$-$MIN $$n$$

times, we get the numbers in the sorted order$).$

Now consider another heap that supports two operations: INSERT and EXTRACTAPPROX$-$MIN, which extracts either the minimum or the second minimum $($but it wont

tell you which one$).$ For example, if the heap contains numbers $15,8,3,11,7,10,$ then

EXTRACT$-$APPROX$-$MIN may return $3$ or $7.$ Prove that it is NOT possible to support

both INSERT and EXTRACT$-$APPROX$-$MIN operations in o$($log n$)$ time.