CS110 4.1 Preclass Work

heapq_max.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


def heappush(lst, item):
    lst.append(item) #append item at the end
    buildmax(lst) #heapify the list starting with root

def heappop(lst):
    p = lst.pop(0) #pop root (which is largest)
    buildmax(lst) #heapify remaining list
    return p #return the popped value

def heappushpop(lst, item):
    lst.append(item) #append item at the end
    p = lst.pop(0) #pop root (which is largest)
    buildmax(lst) #heapify the list starting with root
    return p

def heapreplace(lst, item):
    p = lst.pop(0) #pop root (which is largest)
    lst.append(item) #append item at the end
    buildmax(lst) #heapify the list starting with root
    return p





import random
lst = []
for i in range(100):
    lst.append(int(random.random()*100))
print(lst)

buildmax(lst)
print(lst)

heappop(lst)
print(lst)

heappush(lst,101)
print(lst)

heappushpop(lst,105)
print(lst)

heapreplace(lst,110)
print(lst)