From 6.006 Wiki
Heaps and Heapsort Implementation
# Recitation 08
#
# These functions will help sort the list A[1:] using heapsort.
# Element A[0] may get modified during these operations since we
# will be storing the heap size in this slot.
###Private Helpers
def parent(i):
"""Return the parent index of i or None"""
###INSERT CODE###
pass
def left(i):
"""Return the left child index of i"""
###INSERT CODE###
pass
def right(i):
"""Return the right child index of i"""
###INSERT CODE###
pass
def heap_size(A):
"""Returns the heap size of A"""
return A[0]
def set_heap_size(A, size):
"""Sets the heap size of A to be size"""
A[0] = size
###Public Helpers
def swap(A, i, j):
"""Swaps elements A[i] and A[j]"""
A[i], A[j] = A[j], A[i]
def is_heap_valid(A):
"""Checks if the heap invariant is met"""
for i in range(2, heap_size(A)):
if A[i] > A[parent(i)]:
return False
return True
###Heap functions
def max_heapify(A, i):
"""
Given that the children of A[i] are heaps, create a heap rooted at i
"""
###INSERT CODE###
pass
def extract_max(A):
"""Returns and removes the largest element from A"""
###INSERT CODE###
pass
def build_max_heap(A):
"""Creates a max heap from list A[1:len(A)]"""
###INSERT CODE###
pass
def heapsort(A):
"""Sorts a 1-indexed list A into ascending order"""
###INSERT CODE###
pass
def update_value(A, i, value):
"""Sets A[i] to be value and restores heap invariant"""
###INSERT CODE###
pass
def float_up(A, i):
"""Swaps A[i] with its parent until A[i] < A[parent(i)]"""
if parent(i) and A[parent(i)] < A[i]:
swap(A, i, parent(i))
float_up(A, parent(i))
# Create some sample lists
A = [None, 10, 17, 19, 5, 1, 9, 14, 18, 6, 20, 3, 15, 2, 11, 8, 13, 4, 12, 7, 16]
B = [None, 'cat', 'bat', 'ant', 'dog', 'emu', 'frog']