Python 3 Heap Implementation

heap.py

""
I basically implemented MIT 6.0006 Heap lesson.
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
I stole the index bits from wikipedia.
Mit used arrays starting at 1.
Stole the printing function from:
https://hbfs.wordpress.com/2016/12/06/pretty-printing-a-tree-in-a-terminal/
"""
from collections import deque


def parent(i):
    # Return the index of the parent node
    return (i-1) // 2


def left(i):
    # Return the index of the left child
    return 2*(i)+1


def right(i):
    # Return the index of the right child
    return 2*(i)+2


def build_heap(array):
    # Change the given array into a heap implicit array
    # Implicit means the list itself just stores the heap
    for i in range(len(array)//2, -1, -1):
        heapify(array, i)


def heapify(array, i):
    # Take a given node, i, and move it so the heap property
    # is maintained, which is the root node always is
    # larger than the child nodes
    left_i = left(i)
    right_i = right(i)
    largest = 0

    # Check the left node to see if it's larger
    if left_i < len(array) and array[left_i] > array[i]:
        largest = left_i
    else:
        largest = i

    # Check the right node
    if right_i < len(array) and array[right_i] > array[largest]:
        largest = right_i

    # Repeatly swap the node until heap property is met
    if largest != i:
        array[largest], array[i] = array[i], array[largest]
        heapify(array, largest)


def dfs(array, i=0, depth=0):
    # Print a heap assuming the heap is implemented as an array
    if i < len(array):
        print(f"{' '*depth*4}({array[i]})")
        dfs(array, left(i), depth+1)
        dfs(array, right(i), depth+1)
    else:
        print(f"{' '*depth*4}X")


def bfs(array, start=0):
    # Track nodes visited and to be visited
    quene = deque([start])
    while quene:
        index = quene.popleft()
        print(array[index], end=" ")
        for children in (left(index), right(index)):
            if children < len(array):
                quene.append(children)
    print()


def los(array, start=0):
    # Level order search, similar to bfs but with more crap
    this_level = deque([start])

    while this_level:
        next_level = deque()

        while this_level:
            index = this_level.popleft()
            print(array[index], end=' ')
            for children in (left(index), right(index)):
                if children < len(array):
                    next_level.append(children)
        print()
        this_level = next_level


def heapsort(array):
    # Returns a sorted array using the heap data structure
    sort = []
    build_heap(array)

    while array:
        sort.append(array[0])
        array[0], array[-1] = array[-1], array[0]
        array.pop()
        heapify(array, 0)

    return sort


if __name__ == "__main__":
    array = [x for x in range(10)]

    build_heap(array)
    dfs(array)
    bfs(array)
    los(array)

    print()
    print(heapsort([x for x in range(10)]))