How can I design a sorting algorithm of n elements using a Fibonacci Heap?
Will it be a flavoured version of heap-sort where I replace the heap data-structure with Fibonacci Heap?
Your help is appreciated
1
1
$\begingroup$
$\endgroup$
Designing a sorting algorithm based on the Fibonacci Heap is the same as the Heap Sort; Build the Fibonacci-Heap, Extract Minimum.
From the Wikipedia;
Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular delete and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.
The data size should be very long to achieve better than the heap sort, but this time you may turn into external sort.
And, remember, for comparison based sorting algorithm, we have $\Omega(n \log n)$ as lower bound.
