-1
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

1) The answer is very simple. Assume it can support $delete min$ in less than $log(n)$ time. That means your structure $H$ can sort $n$ elements via comparisons in under $nlog(n)$ time (simply insert all, then $delete min$ $n$ times), which conflicts with the comparison model lower bound.

2) Same as 1. if you can tell who is the minimum element in $O(1)$ and delete it, you can select and delete the minimum $n$ times and therefore sort in under $nlog(n)$ time.

$\endgroup$
  • $\begingroup$ Thanks. There's a thing I'm wondering about though. For part 1), you're saying that for a given list of $m$ numbers, we can do one MAKE-HEAP and $m$ INSERTs. This takes $O(m)$ amortized time. If we could EXTRACT-MIN in $O(\log n)$ amortized time, then we could just call this method $m$ times to get a sorted list in $O(m\log n)$ amortized time. Here $n$ is approximately $2m$, so this would apparently contradict the lower bound for comparison based sorts. $\endgroup$ – HowDoICSharply Mar 21 at 10:40
  • $\begingroup$ And here is my question - is it a contradiction, even though it is amortized time, and not the worst case for a single operation? It seems to happen often that the amortized running time of an operation is strictly smaller than its running time seen as a single operation. $\endgroup$ – HowDoICSharply Mar 21 at 10:40
  • $\begingroup$ if insert is $O(1)$ in amortized time, $m$ inserts cost $O(m) $ worst case, not amortized. $\endgroup$ – lox Mar 21 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.