5
$\begingroup$

If we can insert to a Fibonacci Heap in O(1), and increase-key and find-min in the same W.C time complexity, then why can't we sort an array in time complexity O(n)?

Given an array with n elements:

  1. Find the maximum of the array (largest key) in O(n).

  2. Build a Fibonacci Heap of the elements in O(n), emptying the array in the proccess.

  3. Use find-min and add the result to the now empty array.

  4. Use increase-key on the element you found in step 3, and increase it by the maximum of the old array + 1 (making it now larger than any element of the old array)

  5. Reapet steps 3 and 4, n times. Each time a new element from the old array is added, because all added elements are larger than max+1.

$\endgroup$
8
$\begingroup$

Increase-key is not a $O(1)$ operation on Fibonacci heaps. You're thinking of decrease-key.

Exercise: Why can't increase-key be a $O(1)$ operation on this data structure?

$\endgroup$
  • $\begingroup$ Because you must reorder the heap which is not O(1) (?) $\endgroup$ – Niklas Rosencrantz Nov 23 '17 at 17:13
  • $\begingroup$ It's not a question of reordering the heap. The problem is that if you increase-key the minimum element, it may take a non-constant amount of time to find the new minimum element. It's constant time for decrease-key. $\endgroup$ – Pseudonym Nov 23 '17 at 23:33
0
$\begingroup$

If it was possible, Heapsort would take $\Theta(n)$ time. This is a contradiction to the lower bound of $\Omega(n\lg n)$ when sorting by comparisons.

$\endgroup$
  • $\begingroup$ This doesn't answer the question. The OP knows its a contradiction, but wants to know what's wrong with his logic. Even if the OP thought his algorithm was real, an independent proof of how the algorithm must be wrong doesn't help locate the error in his argument. "1 > 0" is not an answer to "What is wrong with this proof that 0 = 1?" $\endgroup$ – Nicholas Pipitone Apr 17 '18 at 22:32

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.