CS110 3.2 Preclass Work

heapsort.py

def swap(lst,i,j):
    lst[i],lst[j] = lst[j],lst[i]

def heapify(lst,n,i):
    root = i   # initialize root
    left = 2*i + 1  #define left child
    right = 2*i + 2  #define right child
    if left < n and lst[root] < lst[left]: #if the left child is bigger than root, switch
        root = left
    if right < n and lst[root] < lst[right]: #if the right child is bigger than root, switch
        root = right
    if root != i:  #if either of the previous two if statements are executed, make sure the indices align with the item
        swap(lst,i,root)
        heapify(lst,n,root)

def buildmax(lst): #make the initial maxheap
    n = len(lst)
    for i in range(n,-1,-1):
        heapify(lst,n,i)

def heapsort(lst):
    n = len(lst)
    buildmax(lst)
    for i in range(n-1,0,-1): #get roots one by one,
        swap(lst,0,i)
        heapify(lst,i,0)
    return lst

####test####
import random
lst = []
for i in range(10):
    lst.append(random.sample(range(1,100),10))
    print(lst[i])
    heapsort(lst[i])
    print(lst[i])
    print("\n")



#####preclass work 1a######
preclass1 = [39, 85, 85, 16, 49, 7, 49, 92, 76, 15, 21, 30, 29, 31, 28]
buildmax(preclass1)
preclass1