Recitation08 Notes
From 6.006 Wiki
(Difference between revisions)
m (→Heaps and Heapsort Implementation) |
(→Heaps and Heapsort Implementation) |
||
Line 1: | Line 1: | ||
===Heaps and Heapsort Implementation=== | ===Heaps and Heapsort Implementation=== | ||
+ | |||
+ | Download the [http://web.mit.edu/mng_520/Public/rec08_TEMPLATE.py code] | ||
+ | |||
<pre> | <pre> | ||
# Recitation 08 | # Recitation 08 |
Revision as of 18:09, 1 October 2008
Heaps and Heapsort Implementation
Download the code
# 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']