Heapsort – Step 4

• „Take the new tree and make it a heap again“

  • inserting an element can violate the heap property of the tree
  • if so, it has to be exchanged again with its children
  • this needs log n steps in worst case (i.e. if the root has to be moved down through into a leaf position)