In [9]:
# To avoid issues about heap vs array size, we will simply use a Python list, and resize it as needed
# The code is kept as close to the slides as possible. To avoid an index shift, we will place a dummy element (0) at the beginning of the list.
A = [0]
def heap_size(A): return len(A)-1

def Left(i): return 2*i 
def Right(i): return 2*i+1
def parent(i): return i//2

def maximum(A):
    if heap_size(A) < 1: raise Exception('Heap is empty.')
    else: return A[1]

def Heap_Extract_Max(A):
    if heap_size(A) < 1: raise Exception('Heap is empty.')
    max = A[1]
    if heap_size(A) == 1: A = [0]
    else: 
        A[1] = A.pop()
        Max_Heapify(A,1)
    return max

def Max_Heapify(A,i,heapsize=None):
    if heapsize==None: heapsize= heap_size(A)
    if Left(i) <= heapsize and A[Left(i)] > A[i]: largest = Left(i)
    else: largest = i
    
    if Right(i) <= heapsize and A[Right(i)] > A[largest]: largest = Right(i)
    if largest != i: 
        A[i], A[largest] = A[largest], A[i]
        Max_Heapify(A, largest, heapsize)
        
import math

def Insert (A, key):
    A.append(-math.inf)
    Increase_Key(A, heap_size(A), key)

def Increase_Key(A, i, key):
    if key < A[i]: raise Exception('key < A[i]')
    A[i] = key
    while i>1  and A[parent(i)] < A[i]:
        A[parent(i)], A[i] = A[i], A[parent(i)]
        i = parent(i)
        
def Build_Max_Heap(A): # We will assume that A has a dummy element at the beginning
    for i in reversed(range(1,heap_size(A)+1)): Max_Heapify(A,i)

def HeapSort(A):
    Build_Max_Heap(A)
    heapsize = heap_size(A)
    for i in reversed(range(2,heap_size(A)+1)):
        A[1], A[i] = A[i], A[1]
        heapsize -= 1
        Max_Heapify(A,1, heapsize)
In [10]:
A = [0,2,1,3]
HeapSort(A)
print(A)
[0, 1, 2, 3]
In [11]:
import random

A = list(range(1,30))
random.shuffle(A)
A.insert(0,0)
print(A)
[0, 18, 9, 27, 4, 20, 3, 14, 21, 29, 11, 19, 16, 12, 23, 26, 10, 13, 7, 22, 2, 28, 5, 15, 6, 17, 25, 1, 8, 24]
In [12]:
HeapSort(A)
print(A)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
In [27]:
# For completeness below is an implementation that starts at index 0.  
# To avoid issues about heap vs array size, we will simply use a Python list, and resize it as needed

A = []
def heap_size(A): return len(A)

def Left(i): return 2*i+1 
def Right(i): return 2*i+2
def parent(i): return (i-1)//2

def maximum(A):
    if heap_size(A) < 1: raise Exception('Heap is empty.')
    else: return A[0]

def Heap_Extract_Max(A):
    if heap_size(A) < 1: raise Exception('Heap is empty.')
    max = A[0]
    if heap_size(A) == 1: A = []
    else: 
        A[0] = A.pop()
        Max_Heapify(A,0)
    return max

def Max_Heapify(A,i,heapsize=None):
    if heapsize==None: heapsize= heap_size(A)
    if Left(i) < heapsize and A[Left(i)] > A[i]: largest = Left(i)
    else: largest = i
    
    if Right(i) < heapsize and A[Right(i)] > A[largest]: largest = Right(i)
    if largest != i: 
        A[i], A[largest] = A[largest], A[i]
        Max_Heapify(A, largest, heapsize)
        
import math

def Insert (A, key):
    A.append(-math.inf)
    Increase_Key(A, heap_size(A)-1, key)

def Increase_Key(A, i, key):
    if key < A[i]: raise Exception('key < A[i]')
    A[i] = key
    while i > 0  and A[parent(i)] < A[i]:
        A[parent(i)], A[i] = A[i], A[parent(i)]
        i = parent(i)
        
def Build_Max_Heap(A):
    for i in reversed(range(heap_size(A))): Max_Heapify(A,i)

def HeapSort(A):
    Build_Max_Heap(A)
    heapsize = heap_size(A)
    for i in reversed(range(1,heap_size(A))):
        A[0], A[i] = A[i], A[0]
        heapsize -= 1
        Max_Heapify(A, 0, heapsize)
In [30]:
A = [0,2,1,3]
HeapSort(A)
print(A)
[0, 1, 2, 3]
In [31]:
import random

A = list(range(1,30))
random.shuffle(A)
A.insert(0,0)
print(A)
[0, 27, 11, 7, 5, 20, 9, 8, 16, 29, 13, 23, 14, 21, 17, 12, 25, 2, 24, 22, 1, 19, 4, 28, 15, 26, 10, 6, 18, 3]
In [32]:
HeapSort(A)
print(A)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
In [ ]: