CMPT 225 Lecture 6: Lecture 6

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: David Mitchell

Document Summary

Array based heap operations insert(key){ // i == i. I = n while(i > 0 && a[i] < a[(i-1)/2]){ swap a[i] and a[(i-1)/2] For extract-min, we may simplify the code by assuming a is always >=2n and sotring a number larger than the max key in all unused array cells. extract-min(){ Complexity of building a heap from scratch temp = a[0] n = n-1. A[n] = infinity // or a very large number too big to be a key. I = 0 while(a[i] > a[2i + 1] or a[i]>a[2i + 2]){ return temp swap a[i] and a[2i + 1] I = 2i + 1 if(a[2i + 2] > a[2i + 1]) //swap with smallest child else swap a[i] and a[2i + 2] I = 2i + 2 insert and delete-min are both o(logn) Obs o(nlogn) bc n insertions at o(logn)