How much extra space is used by heapsort?

Heapsort is a comparison-based sorting algorithm that allows you to sort a list of elements in ascending or descending order. It is efficient, but not as efficient as some other sorting algorithms, such as quicksort. Here is how it works:

1. Create a heap from the list of elements. A heap is a complete binary tree (that is, a binary tree in which every level is fully filled except possibly the last level and the last level has all keys as left as possible) with the property that the key at the root of the tree is greater than or equal to the keys of its children. There are two types of heaps: max-heaps and min-heaps. In a max-heap, the root node has the maximum key and in a min-heap, the root node has the minimum key.

2. Repeatedly remove the root element (which is the maximum or minimum element in the heap) and insert it into a sorted list.

3. After all the elements have been removed from the heap and inserted into the sorted list, the list will be sorted in ascending or descending order, depending on whether you are using a max-heap or a min-heap.

Heapsort has a time complexity of O(n log n) in the average and worst case and Only O(1) additional space is required. It is not a stable sort, which means that the relative order of elements with equal keys may be different after the sort.