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.