# Heaps and Heapsort

The `.add()` method is used in the `MaxHeap` class to add new values to a max-heap while maintaining the max-heap property that a parent must have a larger value than its children.

`def add(self, element):  self.count += 1  print("Adding: {0} to {1}".format(element, self.heap_list))  self.heap_list.append(element)  self.heapify_up()`

### .heapify_up() Method

The `.heapify_up()` method is used in the `MaxHeap` class to rebalance the heap data structure after an element is added to it.

Starting at the end of the heap where the new element is placed, the new element is compared to its parent value. If the parent has a smaller value than the child, the values swap places. This process repeats itself until an element has no parent value.

`def heapify_up(self):  print("Heapifying up")  idx = self.count  while self.parent_idx(idx) > 0:    child = self.heap_list[idx]    parent = self.heap_list[self.parent_idx(idx)]    if parent < child:      print("swapping {0} with {1}".format(parent, child))      self.heap_list[idx] = parent      self.heap_list[self.parent_idx(idx)] = child    idx = self.parent_idx(idx)  print("Heap Restored {0}".format(self.heap_list))`

### Heapsort

Heapsort is a sorting algorithm that utilizes the heap data structure to sort an unordered list of data.

To implement a heapsort algorithm, take the following steps:

• Add items of an unsorted list into a max-heap.
• While there is at least one element in the heap, remove the root of the heap and place it at the beginning of a list that will hold the sorted values. Whenever the root is extracted, the heap must be rebalanced.
• Once the heap is empty, return the sorted list.
```def heapsort(lst):  sort = []  max_heap = MaxHeap()  # Add items of an unsorted list into a max-heap.  for idx in lst:    max_heap.add(idx)  # While there is at least one element in the heap, remove the root of the heap and place it at the beginning of a list that will hold the sorted values. Whenever the root is extracted, the heap must be rebalanced.  while max_heap.count > 0:    max_value = max_heap.retrieve_max()    sort.insert(0, max_value)  # Return the sorted list  return sort
my_list = [99, 22, 61, 10, 21, 13, 23]sorted_list = heapsort(my_list)print(sorted_list) # Prints: [10, 13, 21, 22, 23, 61, 99]```

### .retrieve_max() Method

The `.retrieve_max()` method is used in the heapsort algorithm to return the largest value in a heap.

In this method, the root of the heap is extracted and replaced by the last element in the heap. Then, the method rebalances the heap data structure using `.heapify_down()`. Finally, the method returns the largest value.

`def retrieve_max(self):  if self.count == 0:    print("No items in heap")    return None  # Store the largest value in a variable  max_value = self.heap_list[1]  print("Removing: {0} from {1}".format(max_value, self.heap_list))  # Replace the root of the heap with the last element in the list  self.heap_list[1] = self.heap_list[self.count]  # Decrease the count  self.count -= 1  # Remove the last element in the list  self.heap_list.pop()  print("Last element moved to first: {0}".format(self.heap_list))      # Rebalance the heap  self.heapify_down()  # Return the largest value  return max_value`

### .heapify_down() Method

The `.heapify_down()` method is used in the heapsort algorithm to rebalance the heap data structure after the root is removed and replaced with the last element in the heap.

While an element contains a child value, the parent value is compared with the value of its largest child. The larger child is determined using the `.get_larger_child_idx()` method. If the parent has a smaller value than the child, the two elements are swapped. Once an element has no children, the heap is restored.

`def heapify_down(self):  idx = 1  # This while loop will execute as long as a child element is present  while self.child_present(idx):    print("Heapifying down!")    # Get the index of the child element with the larger value    larger_child_idx = self.get_larger_child_idx(idx)    child = self.heap_list[larger_child_idx]    parent = self.heap_list[idx]    # If the parent value is less than the child value, swap the values    if parent < child:      self.heap_list[idx] = child      self.heap_list[larger_child_idx] = parent    idx = larger_child_idx  print("HEAP RESTORED! {0}".format(self.heap_list))`

### .get_larger_child_idx() Method

The `.get_larger_child_idx()` method, which is used in the heapsort algorithm, compares the values of an element’s children and returns the index of the child with the larger value.

`def get_larger_child_idx(self, idx):  # Check if a right child exists  if self.right_child_idx(idx) > self.count:    print("There is only a left child")    return self.left_child_idx(idx)  else:    left_child = self.heap_list[self.left_child_idx(idx)]    right_child = self.heap_list[self.right_child_idx(idx)]    # Compare the left and right child values and return the index of the larger child    if left_child > right_child:      print("Left child "+ str(left_child) + " is larger than right child " + str(right_child))      return self.left_child_idx(idx)    else:      print("Right child " + str(right_child) + " is larger than left child " + str(left_child))      return self.right_child_idx(idx)`