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]