Learn

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

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 called max_heap

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.

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?