Great job reaching the end of this lesson and implementing a heapsort algorithm in Python.
Let’s go over what we learned about heapsort:
- A heapsort algorithm uses the heap data structure to organize data.
- The first step to implement heapsort is to place the data inside a heap.
- While the heap has more than one element, extract the largest value in the heap by swapping it with the right-most child and then removing it.
- After we swap the root value and the last value, we must restructure the heap until every parent has a larger value than their children again.
Take a look at the completed code. Feel free to edit the program to get a better understanding of heaps and heapsort.