In [2]:
# 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 [3]:
A = [0,2,1,3]
HeapSort(A)
print(A)
[0, 1, 2, 3]
In [4]:
import random

A = list(range(1,30))
random.shuffle(A)
A.insert(0,0)
print(A)
[0, 16, 26, 18, 5, 14, 20, 21, 24, 3, 8, 1, 17, 28, 23, 2, 12, 27, 10, 9, 6, 29, 22, 4, 19, 13, 7, 11, 15, 25]
In [5]:
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 [6]:
# For completeness below is a version with the index of the heap starting at index 1 (as e.g. in the Cormen et al. book)
# 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 [7]:
A = [0,2,1,3]
HeapSort(A)
print(A)
[0, 1, 2, 3]
In [8]:
import random

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