Heapsort algorithm (Java)

Heapsort algorithm details:

Worst-case Time Complexity: O(n log(n))

Space Complexity: O(1)

 

The algorithm

The heapsort algorithm is an in-place, comparison based sorting algorithm. In the core of the algorithm (as the name suggest), the use of the heap data structure is improving the time complexity. In a nutshell, heap is a special type of tree, where the elements in the tree are in a certain order to each other. This allows to find the minimum or maximum of binary heap in O(1) and insertion/deletion in O(log(n)).

Heapsort is done in two parts, as first step a sub section of the collection is selected. The elements are reordered to be in max heap format, which is O(n) (where n is the selected chunk). From here the algorithm is comparing the “heapified” part of the collection, with the not ordered part recursively until no elements are left to compare. In this process the compared elements are swapped if necessary.

The performance of the heapsort algorithm is O(n log(n)) which is very impressive. I would suggest to use a default library, in a real world application as most of the languages nowadays are implementing a better performing algorithm as default sorting option. In Java the Util package contains a sort method, in the Arrays class. Based on the documentation the implementation is Dual-Pivot Quicksort which performs O(n log(n)) time complexity.

 

Java implementation

My implementation of the heapsort algorithm in java:

The above code snippet is using the Comparable interface, to simplify the code. It allows to define the sorting order as ascending or descending.

The complete implementation with unit tests is available in my Java Algorithms Github Repo, https://github.com/pete314/algorithms-java

 

 

 

• Algorithms
• Data Structures
• Java
• pete
• Sorting