Learn how to implement a heapsort algorithm in Python.

Heapsort: Python

We have all the methods we need in order to create our `heapsort()` function!

Currently, our `heapsort()` function does the following:
* Creates an empty list that will hold our sorted values.
* Creates an instance of `MaxHeap`.
* Adds values from our parameter list into our `MaxHeap` instance.


In order to complete the function, here's what we need to do:
* Create a `while` loop that iterates while our heap has at least one element.
* Inside the loop, extract the largest value from the heap and place it at the beginning of the sorted list. Then, re-heapify the heap to ensure it maintains its heap properties.
* Return the sorted list.

Completing the Heapsort Function

Heapsort is a sorting algorithm that utilizes the heap data structure to sort a list in ascending order.

In this lesson, we'll go over how to complete the following tasks in order to build a heapsort method in Python:
* First, add the values of an unsorted list into a max-heap.
* Next, while the heap has at least one item, swap the placement of the heap's largest value with the last value in the heap.
* After the values are swapped, remove the last element in the heap and place it in a list that will be returned at the end. For every time we swap and extract the root, we then must rebalance the heap.
* Finally, return the sorted list.

Let's get started!

Introduction to Heapsort

After swapping our largest value with the last value, our list now looks like this:
```
[None, 23, 22, 61, 10, 21, 13]
```
Our heap is currently in violation of the rule that a parent should always be larger than its children. There's no reason to get discouraged, we've handled this type of problem before, and we can get our `MaxHeap` back in shape!

We'll define a method, `.heapify_down()`, which performs a similar role to `.heapify_up()`, except now we're moving **down** the "tree" instead of up. Inside the method, we will continuously swap values until our heap is restored. 



Heapify Down I

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:
```py
[22, 21, 61, 13, 10, 23, 99]
```
After adding the above values into a max-heap, the new list should look like this:
```py
[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.

Build a Max-Heap

We've got a handy helper to tell us which child element is smaller, so there's nothing standing between us and a pristine heap. 

In the last exercise, we were pretty lucky that we only needed to make one swap in order to rebalance our heap. This isn't always the case though, so we need to make sure our `.heapify_down()` method checks for all the possibilities.

As a reminder, our strategy for implementing `.heapify_down()` will be very similar to `.heapify_up()`, but we'll be moving down the tree. 
Here's the general shape of the method:
```pseudo
starting with our first element...
  while there's at least one child present:
    get the smallest child's index
    compare the smallest child with our element
      if our element is larger, swap with child
    set our element index to be the child
```

We've added another helper method: `.child_present()`. This returns a boolean indicating whether a given index has an associated child element. 

Heapify Down III

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.


Review

Our goal is to **efficiently remove** the maximum element from the heap in order to place it inside of our sorted list. We'll accomplish this task by creating a `.retrieve_max()` method that does the following:
1. Swaps the first and last element.
2. Removes and returns the largest value.
3. Rebalances the existing heap.

Take a look at our example heap:
```py
print(heap.heap_list)
# Outputs: [None, 99, 22, 61, 10, 21, 13, 23]
```
Our internal list mirrors a binary tree. There's a delicate balance of parent and child relationships we would ruin by directly removing the maximum element, `99`. 

The solution to this problem is to swap the first and last element. The last element in a heap has no children so we can remove it without disrupting our binary tree structure.

Let's see this in action. Note how the last element `23` becomes the first element in the heap list after calling `.retrieve_max()`:
```py
print(heap.heap_list)
# Outputs: [None, 99, 22, 61, 10, 21, 13, 23]
heap.retrieve_max()
# Returns: 99
print(heap.heap_list)
# Outputs: [None, 23, 22, 61, 10, 21, 13]
```
Terrific! We removed the maximum element with minimal disruption. Unfortunately, our heap is out of shape again with `23` sitting where the maximum element should be.

We'll learn how to rebalance our heap in the next lesson.

Extract the Root

We mentioned `.heapify_down()` is a lot like `.heapify_up()`: we track an offending element in the heap and keep swapping it with another element until we've restored the heap properties.

In `.heapify_up()`, we were always comparing our element with its parent. In `.heapify_down()`, we have two possible elements to swap our root value with: the left child or the right child.

Once again, here is our current heap:
```
[None, 23, 22, 61, 10, 21, 13]
```
In order to restore our heap, we need to select the child with the larger value so that we can place it as the root of the heap. In our example, the two children of `23` are `22` and `61`. Since `61` is the larger child, we'll swap it with `23`. After swapping the values, our list looks like this:
```
[None, 61, 22, 23, 10, 21, 13]
```
Our heap has been restored! 

To accomplish this task, we'll create another method in our `MaxHeap` class called `.get_larger_child_idx()`. Its purpose will be to return the index of the child with the larger value.