MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms Lecture 8 Sorting I Heaps 6 006 Spring 2008 Lecture 8 Sorting I Heaps Lecture Overview Review Insertion Sort and Merge Sort Selection Sort Heaps Readings CLRS 2 1 2 2 2 3 6 1 6 2 6 3 and 6 4 Sorting Review Insertion Sort key n2 algorithm 2 4 6 1 3 2 5 4 6 1 1 2 3 4 5 2 4 5 1 3 5 1 2 4 5 6 6 3 6 2 4 5 6 1 3 3 Figure 1 Insertion Sort Example Merge Sort Divide n element array into two subarrays of n 2 elements each Recursively sort sub arrays using mergesort Merge two sorted subarrays 1 Lecture 8 Sorting I Heaps L n time 2 4 5 7 n auxiliary A space R 1 2 3 6 1 2 2 3 4 5 6 7 6 006 Spring 2008 A 1 n 2 A n 2 1 n 2 4 5 7 1 2 3 6 want sorted A 1 n w o auxiliary space Figure 2 Merge Sort Example In Place Sorting Numbers re arranged in the array A with at most a constant number of them sorted outside the array at any time Insertion Sort stores key outside array n2 in place Merge Sort Need O n auxiliary space n lg n during merging Question Can we have n lg n in place sorting Selection Sort 0 i 1 1 Find minimum value in list beginning with i 2 Swap it with the value in ith position 3 i i 1 stop if i n Iterate steps 0 3 n times Step 1 takes O n time Can we improve to O lg n 2 Lecture 8 Sorting I Heaps 6 006 Spring 2008 2 1 5 4 1 2 5 4 1 2 5 4 1 2 4 5 i 1 n time in place 2 Figure 3 Selection Sort Example Heaps Not garbage collected storage A heap is an array object that is viewed as a nearly complete binary tree 1 16 4 8 2 6 9 5 7 8 9 4 1 2 3 4 5 6 7 8 9 10 3 2 14 16 14 10 8 7 9 7 3 1 Figure 4 Binary Heap Data Structure root A i Node with index i PARENT i 2i LEFT i 2i RIGHT i 2i 1 Note NO POINTERS 3 10 3 2 4 1 Lecture 8 length A Sorting I Heaps 6 006 Spring 2008 number of elements in the array heap size A number of elements in the heap stored within array A heap size A length A Max Heaps and Min Heaps Max Heap Property For every node i other than the root A PARENT i A i Height of a binary heap O lg n MAX HEAPIFY O lg n maintains max heap property BUILD MAX HEAP O n produces max heap from unordered input array HEAP SORT O n lg n Heap operations insert extract max etc O lg n Max Heapify A i l left i r right i if l heap size A and A l A i then largest l else largest i if r heap size A and A r largest then largest r if largest i then exchange A i and A largest MAX HEAPIFY A largest This assumes that the trees rooted at left i and Right i are max heaps A i may be smaller than children violating max heap property Let the A i value oat down so subtree rooted at index i becomes a max heap 4 Lecture 8 Sorting I Heaps 6 006 Spring 2008 Example 1 16 2 4 8 7 3 10 1 9 8 2 6 9 5 7 14 MAX HEAPIFY A 2 heap size A 10 10 3 4 1 16 10 3 2 14 4 8 7 3 10 1 9 8 2 6 9 5 7 4 Exchange A 2 with A 4 Call MAX HEAPIFY A 4 because max heap property is violated 1 16 10 3 2 14 4 8 2 6 9 5 7 8 9 4 Exchange A 4 with A 9 No more calls 1 7 3 10 Figure 5 MAX HEAPIFY Example 5
View Full Document
Unlocking...