HeapQ.py

import sys

def Right(i):
    # right child index
    return 2*i + 2

def Left(i):
    # left child index
    return 2*i +1

def Parent(i):
    # parent index
    return (i-1)//2

def maxHeapify(A,i):
    # it takes the node with index i and puts it in the right position
    # in the heap to make it a maxHeap
    l = Left(i)
    r = Right(i)
    # since we already know that element in index i will be: smaller
    # than the right/left child or higher than both
    # we are storing the index of the higher child in 'largest'
    # which will be the substitution that we need to make, in case that we need to do any substitution
    if l < (len(A)) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < (len(A)) and A[r] > A[largest]:
        largest = r
    # now we already have 'largest' in the index that we want to do the substitution
    # we change values if 'largest' is not our current value 'i'
    # ultimately we recursivelly call maxHeapify in 'largest' to make sure
    # that our element will buble down to the right place it should be
    if largest != i:
        h = A[i]
        A[i] = A[largest]
        A[largest]= h
        maxHeapify(A, largest)
    return A
    
def heappop(A):
    # getting the last value so we can put in the place of the highest value
    last = A.pop()
    if A:
        # if there is elements in the array
        # we will return the highest item
        # and the root will be the last value
        # now we just bubble the root down
        returnitem = A[0]
        A[0] = last
        maxHeapify(A, 0)
        print(A, 'heappop')
        return returnitem
    return last

def heapify(A):
    # calling maxHeapify for every node except the leaves
    # so we can form a max-heap array
    for a in range(int(len(A)//2),-1,-1):
        maxHeapify(A,a)
    print(A, 'heapify')
    return A

def bubbleUp(A, i, key):
    # while is not the root and the parent is smaller than our value
    while i > 0 and A[Parent(i)] < A[i]:
        # we change the parent with current value
        A[i], A[Parent(i)] = A[Parent(i)], A[i]
        # variable i receive parent
        i = Parent(i)
    print(A, 'heappush')
    return A

def heappush(A, key):
    # appending key in the last position
    A.append(key)
    # bubbling it up to have the max-heap property
    return bubbleUp(A, len(A)-1, key)


assert heappush([4,3,2,1], 8) == [8,4,2,1,3]
assert heapify([1,2,3,4,5,6,7,8]) == [8, 5, 7, 4, 1, 6, 3, 2]
assert heappop([8, 5, 7, 4, 1, 6, 3, 2]) == 8