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

march07c.docx

1 Page
122 Views

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
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.