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!
Run the code to get a preview of what our completed program will accomplish.