Insight 30.8.1.
Heapsort runs in \(O(n \log n)\) time.
Section 30.8 Heap Sort Efficiency
Subsection 30.8.1 Time Complexity of Heapsort
The heapsort algorithm can be summarized as:
function heapSort(array):
buildHeap(array)
for i from size(array) - 1 down to 1:
swap array[0] and array[i]
heapifyDown(array, 0, i)
The for loop runs \(n - 2\) times, where \(n\) is the size of the array, or \(O(n)\) times. Each iteration involves a swap (\(O(1)\)) and a call to
heapifyDown. As discussed in Section 30.6, heapifyDown runs in \(O(\log n)\) time. Therefore, the overall time complexity of the for loop is \(O(n \cdot (\log n + 1)) = O(n \log n)\text{.}\)
What about the
buildHeap() function? It looks something like:
function buildHeap(array):
for i from floor((size(array) - 2) / 2) down to 0:
heapifyDown(array, i, size(array))
Analyzing it is more complex. The loop runs approximately \(n/2\) times, of \(O(n)\text{.}\) And we know that
heapifyDown can take up to \(O(\log n)\) time. So a naive analysis might suggest that the total time is \(O(n) \cdot O(\log n) = O(n \cdot \log n)\text{.}\)
However, not every call to
heapifyDown will take that long. Nodes near the bottom of the heap have less distance to travel downwards, so they will complete more quickly. In fact, the total time for all calls to heapifyDown during buildHeap can be shown to be \(O(n)\text{.}\) (See below for details.) Therefore, the overall time complexity of buildHeap() is \(O(n)\text{.}\)
Combining these results, the total time complexity of heapsort is the time to build the heap plus the time to sort the heap, which is \(O(n) + O(n \cdot \log n)\text{.}\) Since the dominant factor is \(O(n \cdot \log n)\text{,}\) the overall time complexity of heapsort is \(O(n \cdot \log n)\text{.}\)
How does this compare to other sorting algorithms? Quicksort and mergesort also run in \(O(n \log n)\) time on average. However, heapsort has the advantage of being an in-place sorting algorithm, meaning it requires only a constant amount of additional space. Mergesort, on the other hand, requires \(O(n)\) additional space. Quicksort is also in-place but has a worse worst-case time complexity of \(O(n^2)\text{.}\) Thus, heapsort is a good choice when memory usage is a concern and consistent performance is desired. In practice, heapsort is often slightly slower than quicksort due to constant factors (inefficient use of the memory cache), but it provides a reliable \(O(n \log n)\) performance regardless of the input data.
Subsection 30.8.2 Build Heap Analysis
To analyze the time complexity of
buildHeap(), we need to consider how many nodes are at each level of the heap and how far each node can potentially move downwards during heapifyDown.
In a complete binary tree, the number of nodes at height \(h\) is \(\frac{n}{2^{h+1}}\text{,}\) where \(n\) is the total number of nodes in the heap. Each node at height \(h\) can move down at most \(h\) levels during
heapifyDown.
Therefore, the total work done by all calls to
heapifyDown can be expressed as:
\begin{equation*}
\sum_{h=0}^{\log n} \left( \frac{n}{2^{h+1}} \cdot h \right)
\end{equation*}
This sum can be solved to \(O(n)\text{.}\)
To see why, imagine the layers of nodes. The bottom layer has about \(n/2\) nodes, each of which can move down 0 levels (since they are at the bottom). The layer above that has about \(n/4\) nodes, each of which can move down at most 1 level. The next layer has about \(n/8\) nodes, each of which can move down at most 2 levels, and so on. Eventually we reach the top layer, which has 1 node that can move down at most \(\log n\) levels. So the total work can be visualized as:
\begin{equation*}
(\frac{n}{2} \cdot 0) + (\frac{n}{4} \cdot 1) + (\frac{n}{8} \cdot 2) + (\frac{n}{16} \cdot 3) + \cdots + (1 \cdot \log n)
\end{equation*}
Simplifying this series by factoring out \(n\) and showing a few more terms gives us:
\begin{equation*}
n \cdot \left( \frac{0}{2} + \frac{1}{4} + \frac{2}{8} + \frac{3}{16} + \frac{4}{32} + \frac{5}{64} + \cdots + \frac{\log n}{n} \right)
\end{equation*}
Clearly this sequence gets smaller and smaller as we go along. The \(\frac{\log n}{n}\) term will approach zero for large values of \(n\text{.}\) If we normalize the denominators to all be 64, we can see that:
\begin{equation*}
n \cdot \left( \frac{0}{64} + \frac{16}{64} + \frac{16}{64} + \frac{12}{64} + \frac{8}{64} + \frac{5}{64} + \cdots \right)
\end{equation*}
The total sum of the terms shown is \(\frac{57}{64}\text{.}\) If we extend the sequence to show one more term, it would be \(\frac{6}{128}\text{.}\) Adding that to our sum gives us \(\frac{57}{64} + \frac{6}{128} = \frac{120}{128} + \frac{6}{128} = \frac{126}{128}\text{.}\) If we keep going, the value will slowly converge towards 2.
If the sequence converges towards 2, then the entire expression converges towards \(n \cdot 2 = O(n)\text{.}\)
Checkpoint 30.8.1.
You have attempted of activities on this page.
