Heap sort first constructs a binary heap from the input and then repeatedly removes the root element while restoring the heap property. Building the heap requires Θ(n) time, and the sequence of removals requires Θ(n log n) time.
Heap Sort Complexity Relation
Heap sort first constructs a binary heap from the input and then repeatedly removes the root element while restoring the heap property. Building the heap requires Θ(n) time, and the sequence of removals requires Θ(n log n) time.
\(T(n) = \Theta(n) + \Theta(n \log n) = \Theta(n \log n)\)
What this formula means
Scientific principle
Principle
Heap construction can be performed efficiently using bottom-up heapification. After construction, each root removal requires restoring the heap property, which takes at most logarithmic time because the heap height is logarithmic.
Derivation
1. Let n be the number of input elements.
2. Bottom-up heap construction takes Θ(n) time.
3. Heap sort performs approximately n root removals to place elements into their final sorted positions.
4. Each removal restores the heap property through a sift-down operation.
5. A binary heap with n elements has height Θ(log n).
6. Each removal therefore takes O(log n) time.
7. Across n removals, the sorting phase takes Θ(n log n) time.
8. Total time is Θ(n) + Θ(n log n) = Θ(n log n).
Final Result
T(n) = Θ(n log n)
Heap Construction
T_build(n) = Θ(n)
Sorting Phase
T_sort(n) = Θ(n log n)
Auxiliary Space
O(1) for a conventional in-place iterative implementation
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
T(n) | Total execution time of heap sort | Time or abstract operation count |
n | Number of elements to be sorted | Elements |
T_build(n) | Time required to construct the heap | Time or abstract operation count |
T_sort(n) | Time required for repeated heap removal and restoration | Time or abstract operation count |
SI units and conversions
Execution Time
Depends on the computational environment
Input Size
Number of elements
Time Complexity
Θ(n log n)
Auxiliary Space
O(1) for conventional in-place implementation
Conditions of use
The algorithm uses a binary heap.
Bottom-up heap construction is used for the linear-time construction bound.
The heap is repeatedly adjusted after removing its root.
The analysis assumes heap comparisons and swaps take constant time.
Limitations and assumptions
The asymptotic complexity does not describe exact execution time.
Heap sort is generally not stable unless additional mechanisms are introduced.
In-place heap sort has O(1) auxiliary storage when implemented iteratively.
The sorting phase remains Θ(n log n) in the best, average, and worst cases.
Cache behavior and memory-access patterns can make practical performance differ from other Θ(n log n) sorting algorithms.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
Estimate the asymptotic work of heap sort for an input containing 1,024 elements. |
| Heap sort has Θ(n log n) time complexity; for n = 1,024, the n log₂ n growth measure is 10,240. |
Compare the asymptotic growth measure of heap sort for input sizes 500 and 1,000. |
| Doubling the input size increases the n log₂ n growth measure by approximately 2.22 times. |
Real-world applications
In-place array sorting
Priority queue processing
Memory-conscious sorting
Worst-case predictable sorting
Algorithm performance comparison
Formula Meaning
Heap sort first constructs a binary heap from the input and then repeatedly removes the root element while restoring the heap property. Building the heap requires Θ(n) time, and the sequence of removals requires Θ(n log n) time.
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.