Class Notes (837,548)
Canada (510,312)
CSC148H1 (92)
Paul Gries (18)
Lecture

feb29c.docx

2 Pages
123 Views
Unlock Document

Department
Computer Science
Course
CSC148H1
Professor
Paul Gries
Semester
Winter

Description
 heaps o Combine priority queue functionality with the performance of trees o Each element has a priority value o Min-heap  Elements with low priority value are removed first (more common) o Max-heap  Elements with high priority value are removed first o Heaps have tree structure; elements are always removed from the top of the heap (i.e. the root)  Heap Properties: All heaps have two major properties o Structure Property:  All heaps are complete trees, assumed to be binary trees  Complete tree = all levels are filled except for the last one, which is filled from left to right. o Heap-Order Property:  (assuming min-heap) Every element’s priority value is smaller than the than the priority values of the elements below it  storing heaps: o Even though heaps have a tree structure, they’re commonly stored in Python lists o Using Node objects involves traversing the tree to find the first empty position, or to find the element to swap with the root o Easy navigation, given current element position.  Parent = (current position-1) / 2  Left child = current position * 2+1  Right child = current position*2 + 2 o Complete tree  efficient use of space. o Quick to find key positions:  Last element (for remove) = len(heap) – 1  First empty position = len(heap)  heap insert o To insert an element into the heap, observe structure property first, then resolve heap-order property.  Add new element to first empty spot in the complete tree.  Then bubble the element up (towards the root) until the priority value of the parent is smaller than its own.  (assumes a min-heap). 1. def insert(L, item): 2. '''Insert the given element into the heap.''' 3. 4. L.append(item) 5. bubble_up(L, len(L)-1) 6. 7. def bubble_up(L, i): # for min-heap 8. '''Bubble up the item at index i, swapping with 9. each parent until the item is heapified.''' 10. 11. while i > 0 and L[i] < L[parent(i)]: 12. L[i], L[parent(i)] = L[parent(i)], L[i] 13. i = parent(i) 14. 15. def bubble_up(L, i): # for max-heap 16. '''Bubble up the item at index i, swapping with 17. each parent until the item is heapified.''' 18. 19. if i > 0 and L[i] > L[parent(i)]: 20. L[i], L[parent(i)] = L[parent(i)], L[i] 21. i = parent(i) 2
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