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


How heapsort works

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.

heapsort

Then we 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. 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.


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 .

Java

Javascript

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.

Java

Javascript

Python


Download

Download heapsort in Java, JavaScript and Python
View how heapsort works
Sorting doodles compilation (YouTube)

What are time complexity and space complexity of heapsort?

Heapsort is based on heap data structure. Since heap is a complete binary tree, the time complexity of heapsort is O(nlogn). As far as space complexity, using iterative solution, no extra space is needed. The space complexity is O(1). Using recursive solution, since recursion needs memory for call stacks, the space complexity is O(logn). Therefore Iteration is more efficient.