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.
The basic steps of the Heapsort algorithm can be divided into two parts.
- 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.
- 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.
|Algorithm||Data Structure||Time Complexity - Best||Time Complexity - Average||Time Complexity - Worst||Worst Case Auxiliary Space Complexity|
|Heapsort||Array||O(n log(n))||O(n log(n))||O(n log(n))||O(n)|