6.006 9. Sorting II: Heaps

MIT OpenCourseWare http://ocw.mit.edu6.006Introduction to AlgorithmsSpring 2008For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. Lecture 9 Sorting II: Heaps 6.006 Spring 2008Lecture 9: Sorting II: Heaps Lecture Overview • Review: Heaps and MAX HEAPIFY • Building a Heap • Heap Sort • Priority Queues (Recitation) Readings CLRS 6.1-6.4 Review Heaps: Parent(i)= �i/2� Left(i)=2i Right(i)=2i +1 Max heap property: A[Parent(i)] ≥ A[i] • MAX HEAPIFY(A, 2)heap size(A) = 10A[2] A[4]←→ • MAX HEAPIFY(A,4)A[4] A[9]←→ 1Lecture 9 Sorting II: Heaps 6.006 Spring 2008Violation 16109341471821234567109816 4147932811012345678910etcO(lg n) timeFigure 1: Review from last lecture Building a Heap A[1 n] converted to a max heap Observation: Elements A[�n/2+1�··· n] are all leaves ··· of the tree and can’t have children. BUILD MAX HEAP(A): heap size(A) = length(A) O(n) times for i ←� length[A]/2� downto 1 O(lg n) time do MAX HEAPIFY(A, i) O(n lg n) overall See Figure 2 for an example. 2Lecture 9 Sorting II: Heaps 6.006 Spring 2008MAX-HEAPIFY (A,5)no changeMAX-HEAPIFY (A,4)Swap A[4] and A[8]161093414718212345671098 4 1 2169101487 3AMAX-HEAPIFY (A,3)Swap A[3] and A[7]161093414718212345671098MAX-HEAPIFY (A,2)Swap A[2] and A[5]Swap A[5] and A[10]161093414718212345671098MAX-HEAPIFY (A,1)Swap A[1] with A[2]Swap A[2] with A[4]Swap A[4] with A[9]161093414718212345671098Figure 2: Example: Building Heaps 3Lecture 9 Sorting II: Heaps 6.006 Spring 2008Sorting Strategy • Build max heap from unordered array • Find maximum element (A[1]) • Put it in correct position A[n],A[n] goes to A[1] New root could violate max heap property but children remain max heaps. • Discard node n from heap (decrement heapsize) Heap Sort Algorithm O(n lg n) BUILD MAX HEAP(A): n times for i =length[A] downto 2 do exchange A[1] A[i]←→ heap size[A] = heap size[A] − 1 O(lg n) MAX HEAPIFY(A, 1) O(n lg n) overall See Figure 3 for an illustration. 4Lecture 9 Sorting II: Heaps 6.006 Spring 2008161093414718212345671098109341471821234567989310 4718212345678161093414718212345671098109341471821234567893247181234567161091416109108not part of heapheap_size = 9MAX_HEAPIFY (A,1)Note: cannot run MAX_HEAPIFY with heapsize of 10MAX_HEAPIFY (A,1)MAX_HEAPIFY (A,1)and so on . . .not part of heapnot part of heapFigure 3: Illustration: Heap Sort Algorithm 5Lecture 9 Sorting II: Heaps 6.006 Spring 2008Priority Queues This is an abstract datatype as it can be implemented in different ways. INSERT(S, X) : inserts X into set S MAXIMUM(S): returns element of S with largest key EXTRACT MAX(S): removes and returns element with largest key INCREASE KEY(S, x, k): increases the value of element x’s key to new value k (assumed to be as large as current value) 6