3
$\begingroup$

Suppose I have a min-heap SH stored inside an array. I can perform the operations:

  • view-min(SH) in $O(1)$
  • extract-min(SH) in $O(\log n)$
  • insert(SH) in $O(\log n)$
  • is-empty(SH) in $O(1)$

If I want to build a max-heap BH from the first one, the naive algorithm I can implement is obviously

BH <- build-heap() 
while not is-empty(SH) do             O(n)
    elem <- extract-min(SH)           -> O(logn)
    insert(BH, elem)                  -> O(logn)
done

whose complexity is obvously $O(n \log n)$ worst case. Is this the best algorithm or there is any algorithm whose complexity is lower? Yes

According to Wikipedia we can at least achieve $O(n)$. Without making any assumption about our array being an heap. Can we use this fact to achieve $O(\log n)$ complexity? No

It should be impossible, because we have to deal with any of the $n$ items at least one time. Does this prove that the conversion is $\Theta(n)$?

$\endgroup$
3
$\begingroup$

You could argue that the level-hierarchy gives more information, but not by much. Assuming a full max-heap of distinct values the $min$ element is on the deepest level of $\frac{n+1}{2}$ nodes. Unless there is some additional ordering to the heap, it would then take $\Omega(n)$ just to find the $min$ element.

$\endgroup$
  • $\begingroup$ You don't need the assumption of a full heap. The minimum is always on the frontier, which is of size $(n+1)/4 < \_ \leq (n+1)/2$. $\endgroup$ – Raphael Aug 23 '17 at 14:34
  • 2
    $\begingroup$ That said, to make this rigorous we can add a adversary argument: If the algorithm looks at only $o(n)$ elements, so in particular not all of the frontier (for some large enough tree). So we hide the new minimum there, at a position the algorithm doesn't check. (Only works for deterministic algorithms, of course.) $\endgroup$ – Raphael Aug 23 '17 at 14:39

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.