Heaps.pdf

insert O(log n) delete min O(log n) A binary tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Smallest element is at the root. For every node X, the key in the parent of X is smaller than the key in X. For any el...

insert O(log n) delete min O(log n) A binary tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Smallest element is at the root. For every node X, the key in the parent of X is smaller than the key in X. For any element in array[i]: the left child is in position 2*i the right child is in position 2*i+1 The parent is in i/2  A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10 11 12 class HeapNode: def __init__(self): self.max_heap_size = 0 self.size = 0 self.elements = None insert Strategy: percolateup insert(9) insert(9) insert(9) insert(9) insert(9) insert(9) insert(9) delete min Strategy: percolatedown delete_min() delete_min() delete_min() delete_min() delete_min() build Take n inputs and place heap them into an empty heap.  n successiveinserts build heap percolate downfrom n/2 to1. for(i=n/2;i>0;i--) percolate_down(i); build heap build heap percolate_down(7) build heap percolate_down(6) build heap percolate_down(5) build heap percolate_down(4) build heap percolate_down(3) build heap percolate_down(3) build heap percolate_down(2) build heap percolate_down(2) build heap percolate_down(1) build heap percolate_down(1) build heap percolate_down(1)  Complete BinaryTrees height: h #of nodes: 2h+1 -1 build heap or height:  log(n) #of nodes:n  Running Time build heap Compute the sum of the heights of all the nodes in the heap.  Running Time h ෍ 2i(h−i) build i=0 heap =2 h+1 −1−(h+1)  2h n O(n) O(n logn)  build heapO(n) performn delete_min operations O(n log n)  31 41 59 26 53 58 97 0 1 2 3 4 5 6 7 8 9 10 build heap 97 53 59 26 41 58 31 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 97 53 59 26 41 58 31 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 97 53 59 26 41 58 31 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 97 53 59 26 41 58 31 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 97 53 59 26 41 58 31 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 59 53 58 26 41 31 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 97 53 59 26 41 58 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 59 53 58 26 41 31 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 58 53 31 26 41 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 58 53 31 26 41 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 58 53 31 26 41 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 53 41 31 26 58 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 53 41 31 26 58 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 53 41 31 26 58 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 41 26 31 53 58 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 41 26 31 53 58 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 31 26 41 53 58 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 31 26 41 53 58 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 26 31 41 53 58 59 97 0 1 2 3 4 5 6 7 8 9 10  n delete maxs 26 31 41 53 58 59 97 0 1 2 3 4 5 6 7 8 9 10