We are looking into Fibonacci heaps in class at the moment, but I am stuck with this problem. Let $H$ be a mergable heap structure, by which is meant a data structure, where each element has a key, and that supports the following five operations (taken from CLRS):
MAKE-HEAP(): Creates and returns a new heap containing no elements.
INSERT($H$, $x$): Inserts element $x$ into $H$.
MIMIMUM($H$): Returns a pointer to the element in $H$ whose key is minimal.
EXTRACT-MIN($H$): Deletes the element from $H$, whose key is minimal, and returns a pointer to this element.
UNION($H_1$, $H_2$): Creates and returns a new heap that contains all elements of heaps $H_1$ and $H_2$.
Furthermore assume that $H$ cannot access the key values of its elements, but that it can only tell if tell if the key of one element is less than, equal to, or greater than the key of another element. Let $n$ be the number of operations performed on $H$.
There are two questions:
1) Show that if $H$ supports MAKE-HEAP and INSERT in $O(1)$ amortized time, then $H$ cannot also support EXTRACT-MIN in $o(\log n)$ amortized time (note little-oh).
2) Show that if $H$ supports MAKE-HEAP, INSERT and MINIMUM in $O(1)$ amortized time, then it cannot support DELETE in $o(\log n)$ time. Here DELETE($H$, $x$) is an operation that deletes the element $x$ from $H$.
I am not sure how to go about doing this, since there is no concrete data structure. It has something to do with $H$ only being able to compare keys, like any comparison based sorting algorithm must run in $\Omega(n\log n)$.