Heapsort

Overview

Belonging to the family of comparison-based sorting algorithms, Heapsort improves on the basic selection sort algorithm by utilizing a logarithmic-time priority queue rather than a linear-time search.

Concept

The basic steps of the Heapsort algorithm can be divided into two parts.

  1. The heap is built out of the array (or list) of data and is placed in an array with the layout of a binary tree.
  2. A sorted array is created by removing the largest element from the heap (the root of the tree from step 1 and is inserted into array. The heap is updated after each removal to maintain the structure of the heap. Once all the elements have been removed from the heap, the result is a sorted array.

Algorithmic Complexity

Big-O

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
HeapsortArrayO(n log(n))O(n log(n))O(n log(n))O(n)

 

Implementation

Java Implementation

Coming soon!

References

Wikipedia: Heapsort

 

<- back