Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It works by first building a max heap from the input data, which ensures that the largest element is at the root of the heap. The algorithm then repeatedly removes the largest element from the heap and places it at the end of the sorted array, reducing the size of the heap until all elements are sorted.
The process of heapifying the data ensures that the heap property is maintained, allowing for efficient retrieval of the largest element. Heap sort has a time complexity of O(n log n) and is not a stable sort, meaning that the relative order of equal elements may change.