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

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

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 EXTRACT$-$

APPROX$-$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(logn)$ time.

$[$Hint: prove that if this is possible, then we can do sorting in $o(nlogn),$ which will give us

a contradiction.$]$