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

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

Two solutions are provided to implement heapsort: iteration and recursion. Since heap is a tree structure, the time complexity of heapsort is O(nlogn). No extra space is need. But recursion needs memory for call stack. iteration is more efficient.


Iteration

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.

Java

Javascript

Javascript


Recursion

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.

Java

Javascript

Python

Download Java, JavaScript and Python code
Heapsort doodle
Data structures and visualization