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.

heapsort doodle

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 .




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.




Download and FAQ

Download heapsort in Java, JavaScript and Python
Merge sort
Sorting doodles compilation (YouTube)

What is heapsort space complexity?

There are two solutions for heapsort: iterative and recursive. 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.

What is heapsort time complexity?

Heapsort time complexity is O(nlogn). Heapsort is based on heap data structure. Since heap is a complete binary tree, the time complexity of heapsort is O(nlogn).