he way down the entire height of our tree. Calling <span class="code-chonk">percolateDown()</span> on a node other than the root results in a better runtime because the value in that node cannot swap down quite as many levels as the root's value could. Thus, our O(n log n) runtime is necessarily an over-estimate.</p>
<p>In lecture, we saw that the worst-case number of swaps (which ultimately governs the runtime for our heapify algorithm) is less than <em>n</em>:</p>
<p style="padding-left: 40px;"><img src="