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 is`22`

and its right child is`61`

. - The children of
`22`

are`10`

and`21`

. - The children of
`61`

are`13`

and`23`

. - 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

**1.**

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`

called`max_heap`

**2.**

Next, we’ll add values from an unsorted list into our max-heap:

- Inside the
`heapsort()`

function, create a`for`

loop that iterates through each element of`lst`

. - Inside the loop, add the current element value to
`max_heap`

. - Outside the loop, print the value of
`max_heap.heap_list`

.