Class Notes (838,457)
Canada (510,890)
CSC148H1 (92)
Paul Gries (18)
Lecture

march07c.docx

1 Page
122 Views
Unlock Document

Department
Computer Science
Course
CSC148H1
Professor
Paul Gries
Semester
Winter

Description
1. def heapsort(L): 2. '''(list) -> NoneType 3. Sort the items in L in non-decreasing order.''' 4. if L: 5. heapify(L) # sort the heap. 6. e = len(L) - 1 # The last index in the heap 7. while e > 0: 8. L[0], L[e] = L[e], L[0] 9. e -= 1 10. bubble_down(L, 0, e) 11. 12. def heapify(L): 13. '''(list) -> NoneType 14. Arrange the items in L in a max heap.''' 15. for i in range(1, len(L)): 16. heapify_bubble_up(L, i) # bubble up each item in the list 17. 18. def heapify_bubble_up(L, i): 19. '''(list, int) -> NoneType 20. Bubble the item at index i in L up to where it belongs in the max heap 21. in L[0 : i + 1]''' 22. 23. # while there is a parent and L[i] > its parent: 24. while i > 0 and L[i] > L[parent(i)]: 25. L[i], L[parent(i)] = L[parent(i)], L[i] 26. i = parent(i) 27. 28. def bubble_down(L, i, e): 29. '''(list, int, int) -> NoneType 30. Bubble the item at index i in L down to where it belongs in the max heap 31. in L[i : e + 1]''' 32. 33. # while
More Less

Related notes for CSC148H1

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit