Heapsort is a fast sorting method based on heap data structure.

### How heapify works in heapsort?

Heapsort uses a method “heapify”: you move the larger element in any subtree to the parent position. After heapifying, an array is turned into a heap data structure. The first element in the array is always the largest one.

Then you move the first element to the last position, and move the last one to the front. Run heapify again for the first (n-1) elements in the array. You get the second largest at the front. Move it to the second to last position. By repeating this process, you can get a sorted array. This is the idea of heapsort.

### Iterative solution

The iterative solution uses remove and heapify methods. remove is to move the first element in the heap (the largest one) to the back of the array, and move the last to the front. Then call heapify. In heapify, a while loop starts from the root, compare the parent value with left and right child. Move the larger child to the parent position. Then move down to lower subtree to continue the process .

## Python

### Recursive solution

In the recursive solution, heapify is a recursive function. It starts from the current position, ie the root of the subtree. Find the child which has the larger value. Swap the value with that child. Then calls itself with the position of the larger child.