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

Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.
Already have an account?