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

# feb29c.docx

2 Pages
123 Views

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
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.