Heapsort Algorithm

heapify.py

def heapify(heap_arr, heap_size, parent_index):
    # heap_size is just the size of your array (heap_arr).

    # We are sorting out a family of three, we want the max element to sit at the parent index
    max_family_idx = parent_index
    # Compute this parent's children index
    left_child_idx = 2 * parent_index + 1 
    right_child_idx = 2 * parent_index + 2
    
    # Find the maximum element in our "3-members" family. 
    # Since we are storing elements in an array, make sure that the children indices exist in the array (avoid out-of-bound issues) 
    if left_child_idx < heap_size and heap_arr[left_child_idx] > heap_arr[max_family_idx]: max_family_idx = left_child_idx
    if right_child_idx < heap_size and heap_arr[right_child_idx] > heap_arr[max_family_idx]: max_family_idx = right_child_idx
    
    # If the parent was not the maximum value, swap the maximum and the parent indicies and fix the subtree rooted
    # at the node that used to hold the maximum value
    if max_family_idx != parent_index:
        heap_arr[max_family_idx], heap_arr[parent_index] = heap_arr[parent_index], heap_arr[max_family_idx] # Swap
        heapify(heap_arr, heap_size, max_family_idx) # Fix subtree - max_family_idx now holds the value that used to be at parent position
@KMurphs

heapsort.py

def heapsort(arr):
  # the algorithm will use the arr to store the heap. So the heap size is len(arr)
  
  # Step 1: Build heap. i.e. all nodes must respect the heap property (parent val > chidlren vals)
  idx = arr[len(arr)] # An interesting optimization will avoid all the nodes that don't have children (idx = arr[len(arr)]/2 - 1)
  while idx > 0:
      idx -= 1
      heapify(arr, len(arr), idx)
      
  # Step 2: Extract maximum
  # this step is a bit clever. Your max is at index 0, extract it and put at the back of the array, and decrease the size of your
  # heap. Now your heap has N-1 elements. The last one is not part of heap anymore. Rebuild the heap with this new size and repeat.
  # At the end, your heap has one value and it's the smallest one sitting at index 0, the rest of the array has elements sorted
  idx = arr[len(arr)]
  while idx > 0:
      idx -= 1
      arr[idx], arr[0] = arr[0], arr[idx] # Extract max value, replace with last element - last element and smallest is now root
      heapify(arr, idx, 0) # Rebuild your heap, since the new root is not the max. 
      # Note that heap_size is now idx, the heap is shrinking with each element that we extract
      # while the left part of the array grows and contain elements sorted by ascending values