Heap sort is a comparison-based
sorting
algorithm that uses a binary heap to sort an array
A binary heap is a complete
binary
tree that satisfies the heap property.
The basic
idea
behind heap sort is to create a heap out of the array to be sorted, and then repeatedly remove the root node of the heap
Heap sort has an average case and worst case time
complexity
of O(n*log(n))
Heap sort is not a stable sort, which means that the relative order of elements with equal keys may be changed by the sort
The
advantage
of heap sort is that it does not require additional memory space to sort the array.
Everything you should know about max heap