|
While the Heapsort is a constant factor slower than the Quicksort for
average data sets, it still has a complexity of
(n log2 n) for
best, worst and average data. It also has some interesting properties
that make it particularly useful for sorting data sets that are too
large to fit into primary computer memory.
As we have seen, the initial heapification operation is a linear time
complexity process. The push-down operation described is only a
variation of the heapify process. In the worst case 2i comparisons
will be needed to fully demote a given node from the root to its
proper place.
| 
Search