title: Heap-sort time complexity deep understanding
body: <p>When I studied the Data Structures course in the university, I learned the following axioms:</p>
  <ol>
  <li><p>Insertion of a new number to the heap takes <strong>O(logn)</strong> in worst case (depending on how high in the tree it reaches when inserted as a leaf)</p>
  </li>
  <li><p>Building a heap of <strong>n</strong> nodes, using <strong>n</strong> insertions, starting from an empty heap, is summed to <strong>O(n)</strong> time, using amortized analysis</p>
  </li>
  <li><p>Removal of the minimum takes <strong>O(logn)</strong> time in worst case (depending on how low the new top node reaches, after it was swapped with the last leaf)</p>
  </li>
  <li><p>Removal of all the minimums one by one, until the heap is empty, takes <strong>O(nlogn)</strong> time complexity</p>
  </li>
  </ol>
  <br>
  <p><strong>Reminder:</strong> The steps of &quot;heapsort&quot; algorithm are:</p>
  <ul>
  <li>Add all the array values to a heap: summed to <strong>O(n)</strong> time complexity using the amortized-analysis trick</li>
  <li>Pop the minimum out of the heap <strong>n</strong> times and place the <strong>i</strong>-th value in the <strong>i</strong>-th index of the array : O(nlogn) time complexity, as the amortized-analysis trick does not work when popping the minimum</li>
  </ul>
  <br>
  <p><strong>My question is</strong>: Why the amortized-analysis trick does not work when emptying the heap, causing heap-sort algorithm to take <strong>O(nlogn)</strong> time and not <strong>O(n)</strong> time?</p>
  <h2>Edit/Answer</h2>
  <p>When the heap is stored in an array (rather than dynamic tree nodes with pointers), then we can build the heap bottom up, i.e., starting from the leaves and up to the root, then using amortized-analysis we can get total time complexity of <strong>O(n)</strong>, whereas we cannot empty the heap minima's bottom up.</p>