Heap Sort
Heapsort is a really cool sorting algorithm. It has an extremely important advantage of worst-case O(n log n) runtime while being an in-place algorithm. Heapsort is not a stable sort. It mainly competes with mergesort, which has the same time bounds, but requires Ω(n) auxiliary space, whereas heapsort requires only a constant amount.
As worst case comparison estimate is lower that in quicksort, heapsort is safer then the latter. And it actually works pretty well in most practically important cases like already sorted arrays (quicksort requires O(n2) comparisons in this case).
Heapsort does not have a locality of reference advantage and thus might runs quicker then alternatives on CPU architectures with small or slow data caches. On the other hand, mergesort has several advantages over heapsort:
Better data cache performance, because it accesses the elements
__________ _____ ____ ___ _____ ______ ____.
__________ ____ __________ __________ _______ _________ _______ _________.
______ ____ _______ _______ ____.
____ ________ _________ ____ _______ ______ _____ _______ __________.
____ _______ ____ _____ __________ _______ ___ __________ ________.
______ ______ ______ ____ __________ _________ ______ _______.
____ ________ ______ ________ _______ ____ __________ ________.
_______ ______ ____ ____ _________ ________ ___ __________ _________.
______ ___ _________ _____ ___ __________ _________ _________ ____ _______ ______.
__________ ________ __________ ____ ________ ________ _____ ____.
_______ ______ ___ ______ ________.
_____ ______ _________ ____ ________ ______ ___ __________ _______ __________ _______.
______ ________ _______ __________ _____ __________.
___ ___ _________ _______ _____ __________ ______ _________ __________ ____.
____ _____ __________ ___ ______ ________ ________ _______ ____ ________ _________.
__________ __________ ________ ____ __________.
________ _________ _________ ____ ________ ___ ______ ________ _______ __________.
______ _______ ______ _________ ________ _________ _________ ___.
______ ___ _______ _____ __________.
________ __________ _____ __________ ______ ____ _________ ______.
_____ _______ ____ _________ _______ _____ _____ _____ ___ ________ _____ _________.
__________ ________ __________ ______ _________ ______ __________ __________ __________ ____ ___ _________.
___ ________ ___ ______ ______ ____ ___ ______ ______ _________.
_____ _________ ______ ______ _________ _______ _______ _______ ______.
_________ __________ ________ _____ _________ _______ _____ ______ __________ ______ __________.
_________ _____ _________ ___ _____ _______ ____.
________ _______ _____ _________ ________ _________ ____ __________ __________ _____.
________ _______ ____ __________ _________ __________ ______ ______.
________ ________ ______ ________ __________.
____ __________ __________ __________ _________ _____ __________ __________ _________ ____ ________ ______.
____ _________ _______ _____ ___ ___.
_______ ____ _______ ____ _____ ___ ____ _______.
__________ ________ __________ ______ _________ ____ _________ ______ __________ ___ _______ ______.
_______ ________ ____ ____ __________ ____.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
✓ Unlock up to 60% of the answer
✓ No payment required