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