Our first step with implementing the heapsort algorithm is to organize our unsorted data by placing it into a heap. For this lesson, we’ll be using a max-heap, which we learned about previously.
As a quick refresher, a max-heap is a binary tree type data structure that stores the largest value at its root. The root can always be found at the first element of heap structure. Max-heaps have one major rule: the parent must contain a larger value than its children.
Take a look at the following list:
[22, 21, 61, 13, 10, 23, 99]
After adding the above values into a max-heap, the new list should look like this:
[None, 99, 22, 61, 10, 21, 13, 23]
Let’s go over some details about this heap:
- We can picture this heap like so:99 / \ 22 61 / \ / \ 10 21 13 23
- The root value of this heap is
99
. Its left child is22
and its right child is61
. - The children of
22
are10
and21
. - The children of
61
are13
and23
. - The
None
value at index 0 is a sentinel value that will terminate a loop when read as input. This sentinel element saves us the trouble of checking whether the list is empty.o:
Instructions
Take a look at the heapsort()
function in script.py. We’ll use this function to build out our heapsort algorithm.
Inside the function, create the following two items:
- an empty list called
sort
- an instance of
MaxHeap
calledmax_heap
Next, we’ll add values from an unsorted list into our max-heap:
- Inside the
heapsort()
function, create afor
loop that iterates through each element oflst
. - Inside the loop, add the current element value to
max_heap
. - Outside the loop, print the value of
max_heap.heap_list
.