Heapsort – How does it work?

• Arrange the elements in a heap

• While there are elements in the heap:

  • extract the greatest element – it is the root node
  • take a leaf element of the tree and place it at the top, so that it is the new root
  • take the new tree and make it a heap again