Heapsort is a sorting algorithm that utilizes the heap data structure to sort a list in ascending order.

In this lesson, we’ll go over how to complete the following tasks in order to build a heapsort method in Python:

• First, add the values of an unsorted list into a max-heap.
• Next, while the heap has at least one item, swap the placement of the heap’s largest value with the last value in the heap.
• After the values are swapped, remove the last element in the heap and place it in a list that will be returned at the end. For every time we swap and extract the root, we then must rebalance the heap.
• Finally, return the sorted list.

Let’s get started!