The objective of this homework is to write a Python program that plays with binary heaps. The Checkin tab on the course website will perform preliminary testing of your code. These tests do not indicate your final grade. They can, however, catch mistakes in your submission. You can re-submit your file as often as you want.

Download heap.txt, and rename it heap.py. Some starter code is provided. Don't change it. It is your job to implement these five functions:

def heapify(A, i, n=None):
    """Ensure that the tree rooted at element i in the list A is a heap,
    assuming that the trees rooted at elements left(i) and right(i) are already
    heaps. Obviously, if left(i) or right(i) are >= len(A), then element i simply does
    not have those out-of-bounds children. In order to implement an in-place heap sort,
    we will sometimes need to consider the tail part of A as out-of-bounds, even though
    elements do exist there. So instead of comparing with len(A), use the parameter n to
    determine if the child "exists" or not. If n is not provided, it defaults to None,
    which we check for and then set n to len(A).

    Since the (up to) two child trees are already heaps, we just need to find the right
    place for the element at i. If it is smaller than both its children, then nothing
    more needs to be done, it's already a min heap. Otherwise you should swap the root
    with the smallest child and recursively heapify that tree.
    if n is None:
        n = len(A)
    if not(i < n):
        # if asked to heapify an element not below n (the conceptual size of the heap), just return
        # because no work is required

def buildHeap(A):
    """Turn the list A (whose elements could be in any order) into a
    heap. Use heapify."""

def heapExtractMin(A):
    """Extract the min element from the heap A. Make sure that A
    is a valid heap afterwards. Return the extracted element."""

def heapInsert(A, v):
    """Insert the element v into the heap A. Make sure that A
    is a valid heap afterwards."""

def heapSort(A):
    """Sort the list A (in place) using the heap sort algorithm, into descending order.
    Start by using buildHeap.
    For example, if A = [4, 2, 1, 3, 5]. After calling heapSort(A), then A should be [5, 4, 3, 2, 1].

Testing your code

When provided with input.txt,
python3 heap.py input.txt
should produce output.txt.

The tester program we are using for preliminary testing on Checkin is available here as heap_tests.txt. Rename it to heap_tests.py after downloading the file.